强连通图有拓扑排序吗

拓扑排序（Topological Sorting）是针对有向无环图（Directed Acyclic Graph，DAG）的一种排序方法，它使得所有的定点都在排列顺序上满足其依赖关系，即在排列中，若存在一条从顶点 A 到顶点 B 的有向路径，则在排列中顶点 A 出现在顶点 B 之前。

而强连通图（Strongly Connected Graph）则是指在一个有向图中，若从其中任意一个顶点出发都能到达所有的其他顶点，则该有向图是一个强连通图。

那么问题来了，强连通图能否进行拓扑排序呢？

从定义上来看，一个有向图如果存在拓扑排序，那么肯定是一个DAG，因为DAG具有拓扑排序的唯一性，而强连通图不是DAG，因为有些定点可以到达另外一些定点，另外一些定点也可以到达该定点。

因此，强连通图的拓扑排序是不存在的。

但是，在强连通图中，可以拆分成多个强连通分量，每个强连通分量内部可以进行拓扑排序，得到一个“分量内”的拓扑序，然后将每个强连通分量的“分量内”拓扑序按照某种规则拼接起来，得到整个强连通图的一个拓扑序。

具体的拼接规则有两种：

1.按照缩点后的DAG中“大小”、“依赖”的关系进行拼接，小的在前、无依赖的在前；

2.按照强连通图中DFS枚举时的后序进行拼接。

从这两个拼接规则可以看出，强连通图的拓扑排序并不唯一，因为强连通分量的划分不唯一，而不同的划分又会导致不同的拼接方式。

因此，当面对强连通图时，我们需要先寻找到强连通分量，再根据不同的问题选择不同的拼接方式，得到相应的拓扑序。