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

This article mainly explains "how topological sorting is sorted". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought slowly and deeply. Let's study and learn how topological sorting is sorted together.

Methods: 1. Find a node with 0 degree in the graph, remove this node from the graph and add it to sequence E; 2, remove all associated edges of the nodes found in 1 from the graph; 3, repeat 1 and 2 until all nodes in the graph are removed or nodes with 0 degree can not be found.

The operating environment of this tutorial: windows7 system, Dell G3 computer.

Find a node with a degree of 0 in the graph, remove the node from the graph and add it to sequence E.

Remove all associated edges of the nodes found in 1 from the graph

Repeat 1 ~ 2 until all the nodes in the graph are removed or a node with a degree of 0 cannot be found.

If the number of nodes in the graph is 0, the topological sequence is found. If the number of nodes in the graph is not zero, it means that there are rings in the graph, and the topological sorting cannot be carried out.

Extended data:

The topological ordering of a directed acyclic graph (Directed Acyclic Graph abbreviated as DAG) G is to arrange all the vertices in G into a linear sequence so that any pair of vertices u and v in the graph, if the edge ∈ E (G), then u appears before v in the linear sequence. Usually, such a linear sequence is called a sequence satisfying topological order (Topological Order), which is referred to as a topological sequence. To put it simply, a total order on a set is obtained from a partial order on a set, which is called topological sorting.

Execution steps

The topological sorting algorithm for constructing topological sequences from AOV nets mainly performs the following two steps in a loop until there are no vertices with degree 0.

(1) Select a vertex with a degree of 0 and output it

(2) remove this vertex and all outgoing edges from the net.

At the end of the loop, if the number of vertices output is less than the number of vertices in the network, the "loop" information is output, otherwise the output vertex sequence is a topological sequence.

Thank you for your reading, the above is the content of "how is topological sorting". After the study of this article, I believe you have a deeper understanding of how topological sorting is sorted. The specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.