pseudocode - 拓扑排序伪代码

Question

我有以下拓扑排序的伪代码

Repeat:
Find a vertex with no successor
Remove it from graph
Put It at beginning of list
Until graph is empty

我的问题是，是否应该将其修改为“查找没有前任的顶点”？

Answer 1

是的，它应该。继任者没有意义，当然，除非您在执行拓扑排序之前反转了所有边。

Answer 2

拓扑排序是一种绘制所有边都向前（水平）的图形的方法。假设你有一个图 G（G 应该是一个 DAG）并且你想做一个拓扑图。拓扑排序的伪代码：重复：找到一个没有传入边的顶点删除G中的顶点和边将它放在列表的开头直到图为空

您还可以使用 DFS 进行拓扑排序。那就是在你的 G 上运行 DFS，每次完成一个顶点时，都会在拓扑排序列表的头部插入它的标识符。当 G 中的所有顶点都被发现时，完成的列表就是拓扑排序。该算法的时间复杂度与 (V + E) 的大 O 的 DFS 相同。