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

Question

我可以使用 DFS 算法确定有向图的拓扑排序。如果没有循环，我认为我发现的拓扑顺序是有效的。如果存在循环，我认为拓扑顺序是无用的。到目前为止我是否正确？

无向图呢？“拓扑类型的无向图”是一个有效的陈述吗？对于拓扑排序，图是否必须是有向无环图？

Answer 1

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

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