algorithm - 遍历时拓扑排序？

Question

是否可以在遍历有向无环图时对其进行拓扑排序？

适用于我的情况的额外条件之一是，在我的 DAG 中始终恰好有一个顶点没有传入边。 (我的案例是编译中的文件依赖结构，只有一个入口文件。)

我想知道是否可以在遍历图形时构建拓扑排序的列表，而不是先找到每个顶点然后再排序。

Answer 1

您可以通过运行遍历图的修改后的 DFS 来找到拓扑排序的 DAG 图:

来自 Wikipedia :

An algorithm for topological sorting is based on depth-first search. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node):

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 


 function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

如果你用谷歌搜索，你可以找到很多实现，你可以找到一个实现 here .