拓扑排序

Question

bobo老师，你说拓扑排序只在有向图中才存在这个算法。不过我在几个星期前看b站零神讲解个人赛的追逐游戏时候他说：对无向图做一次拓扑排序其实就相当于把环找出来。对此我还特地记住了，记在了笔记上，然后买了这门课程去学拓扑排序。

具体的链接https://www.bilibili.com/video/BV1si4y1u7KV?p=2，在11：35这个进度条。所以我想问一下bobo老师这是怎么回事？是不是无向图也可以拓扑排序?

Answer 1

liuyubobobo 2021-02-09 05:06:57

在无向图上没有拓扑排序。因为拓扑排序的概念首先建立在有向边上。一个有向边 u->v，从 u 到达 v，拓扑排序才认为 u 在 v 的前面。对于无向边，没有 u 和 v 的前后关系的概念，也就没有排序的概念。

他在这个视频中说的，只是这个算法思路看上去向拓扑排序而已。但不是严格意义的拓扑排序。说成是“用拓扑排序的思路”更合适。这就像很多时候，我们解决问题的思路，是归并排序的思路，但不是严格意义的归并排序。如果你会拓扑排序，应该会容易能把他的这个思路对应的代码写出来。

实际上，这个思路基于这张图是一个有 n 个顶点，n 条边的特殊图，所以肯定有且只有一个环。你也可以理解成，实际上，这个思路基于这张图，创建了一个有向图。这个有向图的创建方式是这样的：

因为这个图，肯定有且只有一个环。这个环上的点我们叫层数 0；从层数 0 能到达的非环上的点叫层数 1；从层数 1 能到达的还没访问过的点叫层数 2，以此类推。这个有向图中的每条有向边，就是在原来无向边的基础上，加一个方向，这个方向是层数高的节点，指向层数低的节点。

依然是，定义了方向，才有点的前后顺序的概念，才有排序的概念。只不过这个隐含的有向图，在算法中，我们不需要把它显式创建出来。这就像课程之前讲的，很多问题，虽然是图论问题，但我们并不需要把这个图创建出来。

P.S.

力扣上的这个问题，和 codeforces 上一个比赛的问题，所处理的图是一样的。（其实这是一类很经典的图，n 个顶点，n 条边）

https://codeforces.com/contest/1454/problem/E (找到这道题累死我了...)

你可以看一下这个问题的官方题解，不会说这是一个基于无向图的拓扑排序的。（我认为你在任意一本严谨的计算机科学教材上，都不会看到无向图的拓扑排序的）

https://codeforces.com/blog/entry/84984

关键摘录如下，there is another approach without any graph algorithms that works very well for such kind of graphs：

继续加油！：）

• 提问者 梦想强大的人i #1

  哇！特别喜欢bobo老师认真负责的样子，谢谢bobo老师啦！