Shulou(Shulou.com)06/03 Report--

Today, I will talk to you about how to use the detection cycle, many people may not know much about it. In order to make you understand better, the editor has summarized the following contents for you. I hope you can get something according to this article.

Today's supplementary topic for CodeTop is to detect circular dependencies.

Circular dependency detection. For example, [['A','B'], ['B','C'], ['C','D'], ['B','D']] = > false, [['A','B'], ['B','C'], ['C','A']] = > true (2021.4-byte jump-happy lane-back end) [2]

Hand-torn code: Xiao Wang wrote a makefile in which n compiled items were numbered 0~n-1, and they were dependent on each other. Please write a program to parse the dependency and give a feasible compilation order. (2021.03 byte beat-system Department-back end) [3]

Some interviewers ask to judge whether there is circular dependence; others ask for a feasible order.

The sharp weapon to solve this kind of problem is topological sorting.

As long as you can BFS, you will traverse the binary tree hierarchically.

You will soon be able to master the writing of topological sorting.

Topic description

At present, there are n compiled items, numbered 0 ~ nmur1. Given a two-dimensional array, it indicates that there are dependencies between compiled items. For example, [0,1] means that 1 depends on 0.

Null is returned if there is a circular dependency; if there is no dependency, a feasible compilation order is returned.

Topic analysis

If a dependency is given as [[0rem 2], [1je 2], [2pr 3], [2pr 4]], as shown in the figure

As you can see, there is no circular dependency between them.

The feasible compilation sequence is [0mem1mem2jin3reui4], or it can be [1record0re2pence4pd3] and so on.

Topological sorting can find such a sequence. It can be seen that the result of this sequence may not be unique.

The process of topological sorting algorithm:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Select a point with a degree of 0 in the diagram and record it.

Delete the point and all edges that start with it in the graph

Repeat 1 and 2 until the graph is empty or there is no point with a degree of 0.

Use the following figure as an example to see the process of the topological sorting algorithm. Res is used to store the result sequence.

There are two points with a penetration of 0 in the picture, and we choose one of them. For example, select point 0, record to res; delete point 0 and the edge that starts with it.

Then select point 1 and record it as well; delete point 1 and the edge that starts with it.

The point with degree 0 now has only point 2, write it down; delete point 2 and the edge that starts with it.

The same goes for it. Select point 3 and record it; delete point 3 and the edge that starts with it.

Select point 4 and record it; delete point 4 and the edge that starts with it.

The picture is empty and the algorithm is over.

In the end, what res stores is the result of topological sorting, that is, the feasible compilation order in the topic.

What if there are circular dependencies in the diagram?

For example, the dependencies are [[0rem 1], [1jue 2], [2pr 1], as shown in the figure.

According to the topological sorting algorithm, find the point 0 with a degree of 0, save it, and then delete it.

Then there is no point with a degree of 0, and the algorithm is over!

We found that we can use res.size () = = n to determine whether there are rings in the graph. Where n is the number of points.

This is the topological sorting algorithm.

The code implementation should be well understood ~ We use BFS to implement topological sorting, and points with a degree of 0 are stored in the queue.

Below I provide C++ and Python two versions of the code. It is recommended that you memorize it, and it is necessary to memorize some template code.

If you don't have a problem with topological sorting, try Leetcode210. II the class schedule.

PS: students who have not been exposed to diagrams before may not quite understand the g that stores the structure of diagrams in the reference code. It's actually very simple, for the following picture.

G = [[2] # means 0-> 2 [2] # means 1-> 2 [3, 4] # means 2-> 3 [3] #-> 4 [] # indicates that there is no edge []] # starting with 3 indicates that there is no edge reference code starting with 4.

C++ version

Vector haveCircularDependency (int n, vector & prerequisites) {vector g (n); / / adjacency table storage graph structure vector indeg (n); / / vector res; of each point / / Storage result sequence for (int I = 0; I < prerequisites.size (); I + +) {int a = prerequisites [I] [0], b = prerequisites [I] [1]; g [a] .push _ back (b) Indeg [b] +;} queue Q; / / enroll all points with zero entry degree at one time for (int I = 0; I < n; I + +) {if (indeg [I] = 0) q.push (I);} while (q.size ()) {int t = q.front (); q.pop (); res.push_back (t) / / when you delete an edge, the penetration of the end point is-1. If the enrollment degree is 0, join the for decisively (int I = 0; I < g [t] .size (); I + +) {int j = g [t] [I]; indeg [j] -; if (indeg [j] = 0) {q.push (j) } if (res.size () = = n) return res; else return {};}

Python version

Def haveCircularDependency (self, n: int, prerequisites): G = [[] for i in range (n)] # adjacency table storage graph structure indeg = [0 for i in range (n)] # the penetration of each point res = [] # Storage result sequence Q = deque () # add dependencies to the adjacency table g And each point penetration for pre in prerequisites: a, b = pre [0] Pre [1] g [a] .append (b) indeg [b] + = 1 # enroll all points with 0 degree in the queue at once for i in range (n): if indeg [I] = = 0: q.append (I) while Q: t = q.popleft () res.append (t) # when deleting edges The degree of entry of the end point is-1. If the entry degree is 0, decisively join the team for j in g [t]: indeg [j]-= 1 if indeg [j] = 0: q.append (j) if len (res) = = n: return res else: return [] after reading the above, do you have any further understanding of how to use the detection loop? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.