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

Question

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

那么无向图呢？ “拓扑结构的无向图”是有效的陈述吗？该图是否应该针对拓扑排序必须是有向无环图？

Answer 1

很难确定无向图的拓扑顺序的含义或外观。有向图的拓扑顺序是这样的:对于图中的每个边(u，v)，u出现在v之前的顺序中。如果您有向图，则边(u，v)和(v，u)彼此不同，并且边缘具有清晰的起点和终点。

但是，在无向图中，边没有起点和终点-节点彼此相邻或彼此不相邻。那么，拓扑顺序是什么样的？给定一条边{u，v} = {v，u}，哪个节点在排序中必须排在第一位是模棱两可的，因为两个节点都不占据另一个节点的特权位置。