directed-acyclic-graphs - 拓扑排序：图

Question

我看了一个关于拓扑排序的类似问题，但仍然不确定这个概念。

有一些我不确定的问题。

Assuming the DFS visits adjacent nodes in alphabetical order, nd a topological order of
the nodes v 2 V by running the DFS on this DAG G from the source (zero in-degree)
node.

图形

对于以下，我得到了（a，d，c，e，b，f）的拓扑顺序。这会是正确的拓扑排序吗？

标签： directed-acyclic-graphstopological-sort

Answer 1

好吧，拓扑排序可以有多个correct排序，而您拥有的排序是正确的。要记住的是，for every directed edge uv from vertex u to vertex v, u comes before v in the ordering所以在你的图表中，考虑边 a->c（a 必须在 c 之前）c->e（c 必须在 e 之前）e->f（e 必须在 f 之前）和很快。