遍历时拓扑排序？
Topological sort while traversing?
是否可以在遍历有向无环图的同时进行拓扑排序？
适用于我的情况的额外条件之一是，在我的 DAG 中始终只有一个顶点没有传入边。 （我的案例是编译中的文件依赖结构，只有一个入口文件。）
我想知道是否可以在遍历图形时构建拓扑排序列表，而不是先找到每个顶点然后再排序。
您可以通过 运行 遍历图的修改 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
如果你 google 它，你可以找到很多实现，你可以找到一个实现 here。
是否可以在遍历有向无环图的同时进行拓扑排序？
适用于我的情况的额外条件之一是，在我的 DAG 中始终只有一个顶点没有传入边。 （我的案例是编译中的文件依赖结构，只有一个入口文件。）
我想知道是否可以在遍历图形时构建拓扑排序列表，而不是先找到每个顶点然后再排序。
您可以通过 运行 遍历图的修改 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
如果你 google 它，你可以找到很多实现，你可以找到一个实现 here。