8.4 图的连通性—有向图的连通性
有向图的连通性不同于无向图的连通性，可分为弱连通、单侧连通和强连通。这里仅就有向图的强连通性以及强连通分量的判定进行介绍。
深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构，则求强连通分量的步骤如下：
（1）在有向图G 上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS 函数)的顺序将顶点排列起来。此时需对8.3.1中的算法作如下两点修改：（a）在进入DFSTraverseAL 函数时首先进行计数变量的初始化，即在入口处加上count=0 的语句；（b）在退出函数之前将完成搜索的顶点号记录在另一个辅助数组finished[vexnum] 中，即在函数DFSAL 结束之前加上finished[++count]=v 的语句。
（2）在有向图G 上，从最后完成搜索的顶点（即finished[vexnum-1]中的顶点）出发，沿着以该顶点为头的弧作逆向的深度搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，依次类推，直至有向图中所有顶点都被访问到为止。此时调用DFSTraverseAL 时需作如下修改：
函数中第二个循环语句的边界条件应改为v 从finished[vexnum-1]至finished[0]。
由此，每一次调用DFSAL 作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。
例如图8.14 (a) 所示的有向图，假设从顶点v1 出发作深度优先搜索遍历，得到finished数组中的顶点号为(1,3,2,0) ；则再从顶点v1 出发作逆向的深度优先搜索遍历，得到两个顶点集{ v1, v3, v4}和{ v2}，这就是该有向图的两个强连通分量的顶点集。
上述求强连通分量的第二步，其实质为：
（1）构造一个有向图Gr，设G=(V,{A})，则Gr=(Vr，{Ar})对于所有< vi,,vj>∈A，必有< vj, vi >∈Ar。即Gr 中拥有和G 方向相反的弧；
（2）在有向图Gr 上，从顶点finished[vexnum-1] 出发作深度优先遍历。可以证明，在Gr 上所得深度优先生成森林中每一棵树的顶点集即为G 的强连通分量的顶点集。
显然，利用遍历求强连通分量的时间复杂度亦和遍历相同。
深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构，则求强连通分量的步骤如下：
（1）在有向图G 上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS 函数)的顺序将顶点排列起来。此时需对8.3.1中的算法作如下两点修改：（a）在进入DFSTraverseAL 函数时首先进行计数变量的初始化，即在入口处加上count=0 的语句；（b）在退出函数之前将完成搜索的顶点号记录在另一个辅助数组finished[vexnum] 中，即在函数DFSAL 结束之前加上finished[++count]=v 的语句。
（2）在有向图G 上，从最后完成搜索的顶点（即finished[vexnum-1]中的顶点）出发，沿着以该顶点为头的弧作逆向的深度搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，依次类推，直至有向图中所有顶点都被访问到为止。此时调用DFSTraverseAL 时需作如下修改：
函数中第二个循环语句的边界条件应改为v 从finished[vexnum-1]至finished[0]。
由此，每一次调用DFSAL 作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。
例如图8.14 (a) 所示的有向图，假设从顶点v1 出发作深度优先搜索遍历，得到finished数组中的顶点号为(1,3,2,0) ；则再从顶点v1 出发作逆向的深度优先搜索遍历，得到两个顶点集{ v1, v3, v4}和{ v2}，这就是该有向图的两个强连通分量的顶点集。
上述求强连通分量的第二步，其实质为：
（1）构造一个有向图Gr，设G=(V,{A})，则Gr=(Vr，{Ar})对于所有< vi,,vj>∈A，必有< vj, vi >∈Ar。即Gr 中拥有和G 方向相反的弧；
（2）在有向图Gr 上，从顶点finished[vexnum-1] 出发作深度优先遍历。可以证明，在Gr 上所得深度优先生成森林中每一棵树的顶点集即为G 的强连通分量的顶点集。
显然，利用遍历求强连通分量的时间复杂度亦和遍历相同。
