我可以使用DFS算法确定有向图的拓扑排序。如果没有循环，我假设我找到的拓扑顺序是有效的。如果存在环路，我认为拓扑顺序就没用了。到目前为止我的说法正确吗？
无向图呢？ “无向图的拓扑排序”是一个有效的陈述吗？为了拓扑排序，图必须是有向无环图吗？
很难确定无向图的拓扑排序意味着什么或看起来是什么样子。有向图的拓扑排序是对于图中的每条边 (u, v)，u 出现在 v 之前的顺序。如果有向图，则边 (u, v) 和 (v, u)彼此不相同，并且边缘有明确的起点和终点。
然而，在无向图中，边没有起点和终点——节点要么相互相邻，要么相互不相邻。那么拓扑排序会是什么样子呢？给定一条边 {u, v} = {v, u}，哪个节点在排序中必须排在第一位是不明确的，因为没有一个节点比另一个节点占据特权位置。
拓扑排序只有在不存在环的情况下才有效。您可以使用决胜局启发式方法，例如从入度最小的顶点断开最后的传出路径。
在这种情况下，最接近您想要的顺序是从此类图的“叶子”到图的质心的顺序。这意味着排序的最右边的项目（或堆栈的顶部）将具有到图中任何其他节点的最小高度（即距离）。
为此，您可以使用卡恩算法的修改版。您不是从 0 入度顶点开始，而是从所有具有 1 入度顶点的叶子开始。请记住，在无向图中，所有节点的边都是双向的，因此不可能有 0 入度的顶点。然后删除所有 1 个入度顶点，推送到堆栈，更新其他顶点的入度顶点并重复，直到图中的所有顶点都已添加到堆栈中。
使用 DFS 在这里没有意义，因为您的结果将根据您选择的图中源顶点的顺序而变化。
编辑无向的情况并充实使用图形的质心将无向转换为有向的想法 - 您可以按如下方式使用该想法： 从每个顶点 v 开始，并从它执行 dfs，假设您遍历到任何未访问节点的边是有方向的（也将边标记为已完成，因此不可能出现反向路径）并计算每个此类遍历遇到的最大深度并存储它适用于每个节点。 所有节点之间的最小深度是图的质心（例如，实际用途将是飞行图中的中心，因为它可以轻松访问所有其他区域）。
现在使用从质心开始的 dfs 遍历来生成有向图，然后生成拓扑排序。 （您可以使用首次看到算法的时间或卡恩的删除 0 入度顶点，减少邻居并添加到堆栈逻辑）