算法中循环图的完成时间及强连通性判定问题

一、完成时间的定义 #

在深度优先搜索（DFS）遍历图的过程中，每个节点会被标记两个时间戳：

• 发现时间：第一次访问该节点时的时间戳
• 完成时间：当该节点的所有邻接节点都被遍历完毕（即针对该节点的递归DFS调用完全结束）时的时间戳

完成时间通常用递增的整数序列记录，遍历开始时时间计数器初始化为0，每完成一个节点的递归遍历，计数器加1并赋值为该节点的完成时间。

二、利用完成时间判断强连通图的方法 #

判断一个图是否为强连通图，常用结合反转弧方向的Kosaraju算法，核心步骤如下：

1. 对原图执行一次DFS遍历，记录每个节点的完成时间
2. 按照完成时间从大到小的顺序，对反转图（将原图所有边的方向反转得到的图）执行DFS遍历
3. 若反转图的这次DFS遍历仅得到一个连通分量，则原图是强连通图；反之则不是

三、反转弧方向方法的原理 #

1. 强连通分量的不变性：原图中的任意强连通分量（SCC），在反转图中依然是一个强连通分量——因为SCC内部节点两两可达，反转所有边后，内部节点的可达关系不会改变。
2. 跨分量边的时间戳特性：假设原图中有两个不同的SCC：A和B，且存在从A到B的边（但B到A无连通边）。原图DFS遍历中，会先进入A，再通过这条边访问B，B的所有节点会先完成遍历（完成时间更小），A的节点会在B全部完成后才结束遍历（完成时间更大）。
3. 反转图的遍历逻辑：反转图中A到B的边变为B到A的边，但原图中B到A无连通边，所以反转图中也不存在A到B的边。按完成时间从大到小（先处理A的节点）遍历反转图时，只会遍历A内部节点，无法到达B；若原图是强连通的，反转图中所有节点依然两两可达，第一次DFS就能遍历全部节点。

内容的提问来源于stack exchange，提问作者ali Mustapha