Topological Sort Chinese version address
Topological sorting means ordering a Directed Acyclic Graph(DAG) to get an ordered linear sequence.
In this way, it may be understood more abstractly.
For example, a project consists of four subsections A, B, C, and D, and A depends on B and D. C depends on D. Now to develop a plan to write A, B, C, D the order of execution. At this point, you can use topological sorting, which is used to determine the order in which things happen.
In topological sorting, if there is a path from the vertex A to the vertex B, B appears behind the A in the ranking result.
- Create a queue Q and a topological ordered result queue T.
- Put all the nodes that do not depend on the vertex in the Q.
- When Q has vertices, perform the following steps.
- Take a vertex n from Q (delete n from Q) and put it in T (add n to the result set).
- For every adjacent point m (n is the starting point and m is the ending point).
- Remove the edge (n, m).
- If m does not depend on the vertex, put b into Q.
The vertex A does not depend on the vertex, which means there is no edge to the end of the A.