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

Question

我可以使用深度优先搜索算法确定有向图的拓扑排序。如果没有环路，我认为我找到的拓扑顺序是有效的。如果存在一个环路，则我认为该拓扑顺序是无用的。到目前为止，我的理解正确吗？

那么对于无向图呢？"无向图的拓扑排序"是一个有效的说法吗？图必须是有向无环图才能进行拓扑排序吗？

- Mehmed

Answer 1

很难确定无向图的拓扑排序是什么意思或者看起来像什么。有向图的拓扑排序是指对于图中的每条边（u，v），在排序中 u 出现在 v 之前。如果你有一个有向图，那么边缘（u，v）和（v，u）不同，并且边缘具有清晰的起点和终点。

然而，在无向图中，边缘没有起点和终点 - 节点要么相互相邻，要么相互不相邻。那么拓扑排序会是什么样子呢？给定边缘 {u，v} = {v，u}，哪个节点先出现在排序中是不明确的，因为两个节点没有优越位置。

- templatetypedef

Answer 2

在这种情况下，您需要的最接近的排序是从此类图的“叶子”向其质心前进的排序。这意味着排序的最右侧项目（或堆栈顶部）将具有到图中任何其他节点的最小高度（即距离）。 为此，您可以使用Kahn算法的修改版。您不需要从0入度顶点开始，而是从所有叶子的1入度顶点开始。请记住，在无向图中，所有节点的边缘都是双向的，因此不可能有0入度顶点。然后您删除所有1入度顶点，将其推入堆栈中，更新其他顶点的入度，并重复此过程，直到图中的所有顶点都添加到堆栈中。 在这里使用DFS没有意义，因为您的结果将基于您选择的源顶点在图中的排序而异。

- arviman