(v); 

        } 

        // 打印每个连通分量中的顶点 

        for (int i = 0; i < M; i++) { 

            for (int v : components[i]) { 

                System.out.print(v + " "); 

            } 

            System.out.println(); 

        } 

    } 

} 

针对一幅具体的有向图，我们来看看Kosaraju算法的轨迹。左侧的图是对反向图作DFS，获得逆后序分列是一个伪拓补序列;在右侧的图中，原有向图按照这个序列进行DFS，总共对5个顶点进行了DFS，每次DFS都表示一个强连通分量(方框框起来的顶点集合)。

膳绫擎代码中的测试样例其实就是膳绫擎这个图。它会打印如下信息

5个连通分量 
1  
0 2 3 4 5  
9 10 11 12  
6  
7 8  

比较上图方框圈起来的内容，切实其实实是5个强连通分量。

趁便一提，如不雅将图中的强连通分量缩小成一个顶点，就能获得下图。因为强连通分量和强连通分量之间不会形成环，所以逆后序获得的是真正的拓补序列。回到原有向图中，按照该拓补序列次序DFS(次序是1, 0, 11, 6, 7)，可以发明算法老是优先选择出度为0的顶点，进行DFS后删除该顶点，再大年夜残剩的图中选择出度为0的顶点持续DFS。

【编辑推荐】

1. 大年夜原始数据到数据科学：使非构造化数据构造化，以推动产品开辟
2. 数据流程图和数据构造是需求分析中弗成缺氨赡一环
3. 数据构造与算法之排序—看不懂你来打我吧
4. Java数据构造与算法解析(八)——伸展树
5. 数据构造中你须要知道的关于树的一切

【义务编辑：未丽燕 TEL：（010）68476606】

　　推荐阅读

　　40岁的IT巨人微软 究竟是什么在支撑着它继续前进？

Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践 上周，微软颁布了其2018财年第一季度的财报。毫无不测埠，微软在这一季度大年夜赚了一笔。微软颁布财报后>>>详细阅读

本文标题：数据结构与算法–图论之寻找连通分量、强连通分量

地址：http://www.17bianji.com/lsqh/38858.html

 1/2    1