数据结构与算法–图论之寻找连通分量、强连通分量

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

components[i] = new LinkedList<>();

}

// 将同一个id的顶点归属到同一个链表中

for (int v = 0; v < graph.vertexNum(); v++) {

components[cc.id(v)].add(v);

}

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

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

for (int v : components[i]) {

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

}

System.out.println();

}

法度榜样将打印如下信息

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

比较上图，吻合!

深度优先搜刮的应用——断定无向图是否有环

应用DFS可以很便利地断定一幅无向图是否成环(假设不存在自环和平行边)。

package Chap7; 
 
public class UndirectCycle { 
    private boolean marked[]; 
    private boolean hasCycle; 
 
    public UndirectCycle(UndiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        for (int s = 0; s < graph.vertexNum(); s++) { 
            if (!marked[s]) { 
               // 刚开端没有顶点被拜访过，所以当前正拜访和上一个被拜访的顶点设置为起点s。当dfs被递归调用一次后，当前正拜访的参数v是s的一个邻居点，而上一个被拜访的参数u是s，相符 
                dfs(graph, s, s); 
            } 
        } 
    } 
    // 修悛改的DFS，v表示当前正拜访的顶点，u表示上一个拜访的顶点 
    private void dfs(UndiGraph<?> graph, 	
			 3/8   首页 上一页 1 2 3 4 5 6 下一页 尾页	
			

　　推荐阅读
　　40岁的IT巨人微软 究竟是什么在支撑着它继续前进？
            Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践
            上周，微软颁布了其2018财年第一季度的财报。毫无不测埠，微软在这一季度大年夜赚了一笔。微软颁布财报后>>>详细阅读


本文标题：数据结构与算法–图论之寻找连通分量、强连通分量
地址：http://www.17bianji.com/lsqh/38858.html
 1/2    1