Topological Sort
Step-by-Step Animation
Animation Speed
Elaboration:
?
Topological Sort: This algorithm works on the directed acyclic graph (DAG). It is a linear ordering of vertices such that for every edge uv from vertex u to vertex v, u comes before v.
Algorithm Details:
(1) Start by inserting all nodes that have no incoming edges onto a list
(2) Remove the first element from the list. Then we process it by removing its adjacent edges and update the destionation node's distance, backedge, and number of incoming edges. If the destination node ends up having 0 incoming edges, we append it to the list
(3) Repeat step (2) until the list is empty.
拓扑排序定义：输入一个点，对创建的有向无环图进行拓扑排序，将图中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。也可以理解为，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。