graph - 使用 DFS 算法对有向图和无向图进行拓扑排序

Question

我可以使用 DFS 算法确定有向图的拓扑排序。如果没有循环，我假设我找到的拓扑顺序是有效的。如果有一个循环，我认为拓扑顺序是无用的。到目前为止我是正确的吗？

那么无向图呢？“无向图的拓扑排序”是一个有效的陈述吗？该图是否必须是有向无环图才能进行拓扑排序？

标签： graphgraph-algorithmdirected-acyclic-graphsundirected-graph

Answer 1

很难确定无向图的拓扑排序意味着什么或看起来像什么。有向图的拓扑排序是对于图中的每条边 (u, v)，u 出现在 v 之前的排序中。如果您有有向图，边 (u, v) 和 (v, u)互不相同，边有明确的起点和终点。

然而，在无向图中，边没有起点和终点——节点要么相互相邻，要么相互不相邻。那么拓扑排序会是什么样子呢？给定一条边 {u, v} = {v, u}，哪个节点必须在排序中排在第一位是不明确的，因为两个节点都没有比另一个节点占据特权位置。