How is topological sort sorted?

Method: 1. Find a node in the graph with an in-degree of 0, remove this node from the graph and add it to the sequence E; 2. Associate all the nodes found in 1 The edge is removed from the graph; 3. Repeat steps 1 and 2 until all nodes in the graph are removed or a node with an in-degree of 0 cannot be found.

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

1. Find a node in the graph with an in-degree of 0, remove this node from the graph and add it to the 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 a node with an in-degree of 0 cannot be found Click until

If the number of nodes in the graph at this time is 0, the topological sequence has been found. If the number of nodes in the graph at this time is not 0, it means that there is a cycle in the graph and topological sorting cannot be performed. .

Extended information:

To perform topological sorting on a directed acyclic graph (DAG for short) G is to arrange all the vertices in G into a linear sequence, such that for 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 that satisfies the topological order, or is referred to as a topological sequence. Simply put, from a partial order on a set to a total order on the set, this operation is called topological sorting.

Execution steps

The topological sorting algorithm that constructs the topological sequence from the AOV network mainly performs the following two steps in a loop until there is no vertex with an in-degree of 0.

(1) Select a vertex with indegree 0 and output it;

(2) Delete this vertex and all outgoing edges from the network.

After the loop ends, if the number of output vertices is less than the number of vertices in the network, the "loop" information will be output, otherwise the output vertex sequence is a topological sequence.

For more computer-related knowledge, please visit the FAQ column!

The above is the detailed content of How is topological sort sorted?. For more information, please follow other related articles on the PHP Chinese website!