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

This article is to share with you about what topological sorting is in web development. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Preface

Topological sort, also known as Topological order, is a bit confusing because topological sorting is not a pure sorting algorithm, it just finds a linear order that can be executed for a certain class of graphs.

This algorithm sounds high-end, and today's interviews are also very fond of exams. For example, when I was interviewing our company at that time, I had a whole round of designs based on topological sorting.

But it is actually a very easy to understand algorithm, follow my train of thought, so that you will never forget her.

Directed acyclic graph

As we just mentioned, topological sorting is only for a specific type of graph, so what kind of graph is it?

A: Directed acyclic graph (DAG), directed acyclic graph. That is:

The edges of this graph must be directed.

There is no loop in the picture.

So what is the direction?

For example, Wechat friends is positive. If you add him as a friend, he may delete you but you don't know. Then this friend relationship is one-way.

What is a ring? The ring is related to the direction, and you can return to yourself from a point. This is the ring.

So the picture below is not a ring on the left, but a ring on the right.

So if there is a loop in a graph, such as the figure on the right, if you want to execute 1, you have to execute 3 first, if you want to execute 3, you have to execute 2, and if you want to execute 2, you have to execute 1. This becomes an endless cycle, and you can't find the correct way to open it. So I can't find a topological order of it.

Summary:

If this graph is not DAG, then it has no topological order.

If it is DAG, then it has at least one topological order.

On the other hand, if it has a topological order, then the graph must be DGA.

So this is a necessary and sufficient condition.

Topological sorting

So what does the "topological order" of such a graph mean?

Let's use this course schedule of Baidu encyclopedia to explain.

Course code name advance course C1 Advanced Mathematics without C2 programming Foundation without C3 discrete Mathematics C1, C2C4 data structure C3, C5C5 algorithm language C2C6 Compiler Technology C4, C5C7 operating system C4, C9C8 General Physics C1C9 computer principles C8

There are nine courses, some of which require a prerequisite, that is, you have to take the "required course in the rightmost column" before you can take the "advanced" course.

So the meaning of topological sorting in this example is:

Is to solve a feasible order that allows me to learn all the lessons.

So how do you do that?

First of all, we can use a graph to describe it.

The two elements of a graph are vertices and edges.

So here it is:

Vertex: every course

Side: the course at the beginning is the prerequisite for the course at the end

Draw it and look like this:

This kind of graph is called AOV (Activity On Vertex) network, in this kind of diagram:

Vertices: representing activity

Edge: indicates the priority relationship between activities

So an AOV net should be a DAG, that is, a directed acyclic graph, otherwise some activities will not be carried out.

Then all activities can be arranged into a feasible linear sequence, which is a topological sequence.

So the practical significance of this sequence is:

In this order, at the beginning of each project, it is possible to ensure that its precursor activities have been completed so that the whole project can be carried out smoothly.

Back to our example:

We can see at a glance that we have to learn C1 and C2 first, because there are no requirements for these two courses. We should learn them as freshmen.

As a sophomore, we can learn C3, C5 and C8 in the second line, because the prerequisite courses for these three courses are C1 and C2, and we have all finished.

Junior students can learn C4 and C9 in the third line.

The remaining C6 and C7 will be selected in the last year.

In this way, we finish all the lessons and get a topological sort of the graph.

Note that sometimes the topological order is not unique, for example, in this case, learn C1 before C2, and C2 before C1, are the correct topological order of this graph, but these are two orders.

So during the interview, ask the interviewer whether to ask for any solution or to list all the solutions.

Let's sum up.

The edges in this graph represent a dependency. If you want to take the next course, you have to take the previous course first.

This is the same as in the game, to get a prop, you have to do task A, and then complete task B, and finally reach the destination.

Detailed explanation of algorithm

In the above diagram, you can easily see its topological order, but as the project becomes larger and larger, the dependencies will become complex, so it needs to be solved in a systematic way.

So let's think back to the process of finding the topological order ourselves, why did we fall in love with C1 and C2 in the first place?

Because they don't depend on others.

That is, its degree of entry is 0. 5%.

Entrance degree: the entry degree of a vertex refers to the number of edges pointing to the vertex

Degree: the degree of a vertex is the number of edges that the vertex points to other points.

So let's first implement those points with a degree of zero.

That is to record the entry of each vertex.

Because only when its degree of entry = 0 can we execute it.

In the example just now, the initial entry degree of C1 and C2 is 0, so we can execute these two first.

Then the first step in this algorithm is to get the degree of each vertex.

Step0: pre-processing to get the entry degree of each point

We can use a HashMap to store this information, or an array would be more elaborate.

In order to facilitate the display in the article, I used the table:

C1C2C3C4C5C6C7C8C9 entry 002212211Step1

Once you get this, you can execute these points with an entry degree of 0, that is, C1, C2.

Then we put these points that can be executed into a container to be executed, so that we can take the vertices from this container one by one.

As for which data structure the container chooses, it depends on what we need to do and which data structure can serve it.

So first of all, [C1, C2] can be put into the container.

Then think about what we need to do!

The most common thing we do is to put the point in and take it out for execution, that is, we need a data structure with more efficient offer and poll operations, then queue is enough.

(others are fine. The vertices in this container have the same status, can be executed, and have nothing to do with the order in which they come in, but why bother yourself? A simple queue in regular order will suffice. )

Then you need to take some points out and execute them.

[highlight] when we take out C1 for implementation, what does that mean?

A: it means that the "edge" of "taking C1 as the vertex" and "pointing to other points" has disappeared, that is, the degree of C1 has become 0. 5%.

As shown in the following picture, these two edges can disappear.

At this point, we can update the points pointed by C1, that is, the entry degrees of C3 and C8. The updated array is as follows:

C3C4C5C6C7C8C9 penetration 1212201

Then we see a very crucial step here, the entry degree of C8 has become 0!

This means that C8 does not have any dependencies at this time and can be put into our queue to wait for execution.

At this time our queue is: [C 2, C 8].

Step2

Next, we'll execute C2.

So the entry degree of C3 and C5 pointed to by C2 is-1.

Update the table:

C3C4C5C6C7C9 penetration 020221

That is, C3 and C5 are free of any bondage and can be implemented in queue.

Queue now becomes: [C8, C3, C5]

Step3

So the next step is to implement C8.

The entry degree of C9 referred to by corresponding C8 is-1.

Update the table:

C4C6C7C9 penetration 2220

Then C9 does not have any requirements and can be implemented in queue.

Queue now becomes: [C3, C5, C9]

Step4

Next, execute C3

The corresponding C3 refers to the degree of entry of C4-1.

Update the table:

C4C6C7 entry 122,

However, the degree of entry of C4 has not become 0, so there is no point to add queue.

Queue now becomes [C5, C9]

Step5

Then execute C5

Then the degree of entry of C4 and C6 referred to by C5 is-1.

Update the table:

C4C6C7 entry degree 012

Here the dependence on C4 is all gone, so you can put C4 in queue:

Queue = [C9, C4]

Step6

Then execute C9

Then the degree of entry of C7 referred to by C9 is-1.

C6C7 entry 11

Here the entry degree of C7 is not 0, and you can't join queue yet.

At this point queue = [C4]

Step7

Then execute C4.

So the entry degree of C6 and C7 pointed to by C4 is-1.

Update the table:

C6C7 entry 00

The entry of C6 and C7 has become zero! Put them into queue and continue execution until queue is empty.

Summary

All right, let's comb through this algorithm:

Data structure here our entry table can be stored in map, and students who are not clear about map can read the HashMap article I wrote earlier.

Map:

But in the actual code, it is enough to use an int array to store. Graph node can be represented by the index of the array, and value is represented by the values in the array, which is more sophisticated than Map.

Then a normal queue is used to store the node that can be executed.

In the process, we put the vertices with a degree of 0 into the queue, and then each time we execute the vertices in the queue, we can make the entry of those points that depend on the executed vertex-1. If the penetration of any vertex becomes 0, we can put it into the queue until the queue is empty.

Here are a few implementation details:

When we check whether there is a new vertex entry = = 0, there is no need to go through the entire map or array, just what check has just changed.

The other is that if the problem does not give the condition that the graph is DAG, then there may be no feasible solution, so how to judge? A very simple method is to compare whether the number of vertices in the final result is equal to the number of all vertices in the graph, or add a counter, if not equal, it means that there is no effective solution. So this algorithm can also be used to determine whether a graph is a directed acyclic graph.

The condition given by many topics may be the edge list for the graph, which is also a common way to represent the graph. Then the list given represents the edges in the graph. Here we should pay attention to examining the questions and see clearly who depends on who. In fact, the problem of the picture usually does not give you this picture directly, but to a scene, which requires you to change it back to a picture.

Time complexity

Note ⚠️: the time complexity analysis of the graph must be two parameters, many students open their mouth during the interview is O (n).

For graphs with v vertices and e edges

The first step is to preprocess to get map or array, which needs to go through all the edges, so it is O (e).

The second step is to put the point of entry = = 0 into and out of the team is O (v). If it is a DAG, then all the points need to be in and out of the team once.

The third step is to eliminate the edge it points to every time you execute a vertex, which is executed a total of e times.

Total: O (v + e)

Space complexity

An array is used to store the indegree of all the points, and then the queue also puts all the points in at most, so it is O (v).

Code

With regard to the ranking of courses, there are two questions on Leetcode, one is 207, asking if you can complete all the courses, that is, whether topological sorting exists; the other is 210, which allows you to return any topological order, or an empty array if you can't finish it.

Here we write with the question 210, which is more complete and more frequent.

The input given here is the edge list we just talked about.

Example 1.

Input: 2, [[1,0]]

Output: [0,1]

Explanation: there are 2 courses here, and the prerequisite for 1 is 0. 5%. So the correct order of course selection is [0,1].

Example 2.

Input: 4, [[1,0], [2,0], [3,1], [3,2]]

Output: [0,1,2,3] or [0,2,1,3]

Explanation: here is an example that shows the following figure

Example 3.

Input: 2, [[1,0], [0,1]]

Output: null

Explanation: I can't take this lesson.

Class Solution {public int [] findOrder (int numCourses, int [] [] prerequisites) {int [] res = new int [numCourses]; int [] indegree = new int [numCourses]; / / get the indegree for each course for (int [] pre: prerequisites) {indegree [pre [0]] +;} / / put courses with indegree = 0 to queue Queue queue = new ArrayDeque () For (int I = 0; I < numCourses; iTunes +) {if (indexed [I] = = 0) {queue.offer (I);}} / / execute the course int i = 0; while (! queue.isEmpty ()) {Integer curr = queue.poll (); res [indexed +] = curr / / remove the pre = curr for (int [] pre: prerequisites) {if (pre [1] = = curr) {indegree [pre [0]] -; if (indegree [pre [0]] = = 0) {queue.offer (pre [0]) } return I = = numCourses? Res: new int [] {};}}

In addition, topological sorting can also be achieved with DFS-depth-first search, limited space will not be carried out here, you can refer to this material of GeeksforGeeks.

Practical application

We have already mentioned one of its use case, that is, the course selection system, which is also the most common test question.

The most important application of topological sorting is the critical path problem, which corresponds to AOE (Activity on Edge) networks.

AOE network: the vertex represents the event, the edge represents the activity, and the weight of the edge represents the time required for the activity.

AOV network: vertices represent activities and edges represent dependencies between activities.

In AOE net, the path with the maximum length from the starting point to the end point is called critical path, and the activity on the critical path is called critical activity. AOE network is generally used to analyze the process of a large project, to analyze at least how much time it takes to complete, and how much maneuver time each activity can have.

Specific is how to apply the analysis, you can refer to this video 14 minutes 46 seconds, this example is still very good.

In fact, it is applicable to any graph with dependencies between tasks.

For example, when the pom dependency introduced the jar package, have you ever wondered how it imported some jar packages that you didn't introduce directly? For example, you do not introduce aop's jar package, but it automatically appears, this is because some of the packages you import depend on the jar package aop, then maven automatically imports it for you.

Other practical applications, such as:

Preprocessing of speech recognition system

Manage dependencies between target files, like the jar package import I just said

Network structure processing in in-depth learning.

Thank you for reading! This is the end of this article on "what is topological sorting in web development?". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

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.