利用深度优先搜索来寻找图的强连通分量(未竟)

算法思路

以图来说明

1. 为有向图 G。每个加了阴影的区域是 G 的一个强连通分量。每个结点上注明了在深度优先搜索中的发现时间和完成时间，所有的树边都加了额外的阴影。

2. 是图 G 的转置图 $G^{T}$，图中注明了由算法 STRONGLY-CONNECTED-COMPONENTS 第 3 行所计算出来的深度优先森林，所有树边上都加了额外的阴影。每个强连通分量对应一棵深度优先树。加了阴影的结点 b、c、g 和 h 全部是深度优先树的根节点。这些深度优先树是在转置图 $G^T$ 上运行深度优先搜索算法所获得的。

3. 无环分量图 $G^{SCC}$，由对图 G 的强连通分量进行收缩而成，这种收缩将每个强连通分量收缩为一个结点，即由一个结点来替换整个连通分量。

伪码描述

这里针对第 3 行进行简单说明，$u.f$ 即 G 中的结点 u 在深度优先搜索过程中的完成时间。这行代码所做的事情是按照 $u.f$ 递减的顺序进行循环，然后找出每一棵深度优先数，这每一棵深度优先树就对应一个强连通分量。