求有向图的强连通分量的经典算法——Kosaraju算法一Kosaraju算法.doc

求有向图的强连通分量的经典算法 ——Kosaraju算法 一、Kosaraju算法步骤： Step1、对有向图G做dfs（深度优先遍历），记录每个结点结束访问的时间 Step2、将图G逆置，即将G中所有弧反向。 Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs Step4、得到的遍历森林中每棵树对应一个强连通分量。 相关概念： 在dfs(bfs)算法中，一个结点的开始访问时间指的是遍历时首次遇到该结点的时间，而该结点的结束访问时间则指的是将其所有邻接结点均访问完的时间。 二、Kosaraju算法求解过程实例 下面结合实例说明Kosaraju算法的基本策略。图1给出了一个有向图G。 Step1：假设从DFS在遍历时按照字母顺序进行，根据Kosaraju算法，在步骤1中我们得到的遍历顺序可以表达为 [A,[C,[B,[D,D],B],C],A][E,[F,[G,[H,H],G],F],E] 在遍历序列中每一个结点出现了两次，其中第一次出现的时间为该结点的开始访问时间，第二次出现的时间为该结点的结束访问时间。 Step2：根据算法第2步，将图G逆置，得到对应的反向图G’如图2所示。 Step3：根据步骤1得到的遍历序列，按照结点结束访问时间递减排序后的结果为 EFGHACBD 下面，按照该结点序列顺序对逆置图G’所深度优先遍历，得到的深度优先遍历森林如图3所示。森林中共有4棵树，其中(a)和(d)只有一个结点，这里认为单结点也是一个强联通分量（在实际应用中可以根据实际需要将这种情况过滤掉）。 三、算法讨论 问题1：以上图为例，第一遍有哪些信誉好的足球投注网站得到以A为根的子序列（设为S1）和以E为根的子树序列（设为S2），图反向后，再从E开始有哪些信誉好的足球投注网站，能搜到的元素肯定不会包含S1的元素，为什么？ 答：因为S1中的点都不能到达E，而第二遍有哪些信誉好的足球投注网站就是看哪些点能到达E，所以搜不到S1中的点。 问题2：图反向后对A进行深搜，尽管E能到达A，为什么搜不到E？ 因为第一遍深搜时，A不能达到E，所以E肯定位于A的右边，而第二遍深搜是按照结束时间进行有哪些信誉好的足球投注网站的，在有哪些信誉好的足球投注网站A之前，已经搜完E，对E设置了已经遍历标志，所以不会把E并入A的强联通分量。 四、算法实现 Kosaraju算法是基于DFS算法和图的逆置算法来实现的，这两个基本算法都很简单，关键是需要在第一次DFS时记录结点结束时间，然后在第二次对逆置图遍历时按照结束时间递减顺序再次进行DFS。这一点具体实现时方法很多，比如设置一个整型变量来存储遍历时间，初值为0，并设置一个数组来记录每个结点结束遍历的相对时间。然后在第一次遍历完后按照此顺序对结点排序。 除此之外，还可以借助队列来实现排序功能。回顾一下数据结构里关于DFS算法。完整的深度优先算法由两个函数部分构成，即DFS和DFS_SEARCH，前者是深度优先遍历算法的入口，完成相关辅助变量和数组(如visited)的初始化，然后对于每一个没有访问的结点v，以它为遍历起点调用DFS_SEARCH，一次可以得到一个以v为根结点的深度优先遍历生成树(可以找到所有v结点能够访问到的结点集合)。 根据结点结束访问时间的定义，在某一次调用DFS_SEARCH中，显然遍历时越早遇到的结点，相对结束访问时间也就越晚，因此在这一次调用DFS_SEARCH内结点结束的时间递减顺序与结点首次访问顺序一致。而对于不同次调用DFS_SEARCH，调用越晚其相对结点结束的时间也就越晚。根据上述分析，我们可以在第一次DFS遍历时一次得到内结点结束的时间的递减顺序。 例如，对于图1中的有向图G，仍然按照字典顺序遍历；则第一次对结点A调用DFS_SEARCH时，遍历顺序为ACBD；第二次对结点E调用DFS_SEARCH得到的结点遍历顺序为EFGH，因此最终得到的结点结束的时间递减序列为 EFGHACBD 和上面的计算结果一致。 五、思考题目 Kosaraju算法是计算有向图强连通分量的经典算法。但如果要计算出有向图中所有连通子图，如何做？ 图2 逆置图G’ F E D B H G C A 图1 有向图G H G F E D C B A (a) (b) (c) (d) D C A B H F E G 图3 逆置图G’的DFS生成森林