Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践

找无向图的连通分量

应用深度优先搜刮可以很简单地找出一幅图的所有连通分量，回想连通图的概念：如不雅大年夜随便率性顶点都存在一条路径达到随便率性一?顶点，则称这幅图是连通图。而连通分量指的是一幅图中所有极大年夜连通子图。将整幅图比方成串了幼稚的绳索的话，将随便率性顶点提起，连通图将是一个整体;非连通图散成若干条较小的┞符体，这每一条整体就是一个整幅图的一个连通分量。易知连通图只有一个连通分量，就是它自身;如不雅一幅图的顶点都是分散的，那么连通分量的个数(只有一个顶点)就是图的顶点数个。所以连通分量的数量范围为[1, graph.vertexNum]

下面这幅图，有3个连通分量。

回想深度优先搜刮的过程：它大年夜某个顶点出发，拜访它的某一个邻居点，接着拜访这个邻居点的某一个邻居点….如斯深刻下去，一向达到某个顶点发明四周的邻居点都已经拜访过了，此时往回退到上一个顶点，拜访该顶点的未被拜访过的邻居点…直到所有顶点都被拜访过。很轻易知道，在一次深度优先遍历中所有拜访过的顶点都是互相可达的，或者说是连通的。我们按照Union-Find算法那样，给每个连通分量标示一个id，即竽暌沟有同一个id的顶点归属于同一个连通分量。膳绫擎已经分析过，连通分量的数量范围为[1, graph.vertexNum]，所以须要的id个数graph.vertexNum就足够，存储id的数组int[] id典范围是[0, graph.vertexNum – 1]。

package Chap7; 
 
import java.util.LinkedList; 
 
public class CC { 
    // 用来标记已经拜访过的顶点，包管每个顶点值拜访一次 
    private boolean[] marked; 
    // 为每个连通分量标示一个id 
    private int[] id; 
    // 连通分量的个数 
    private int count; 
 
    public CC(UndiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        id = new int[graph.vertexNum()]; 
        for (int s = 0; s < graph.vertexNum(); s++) { 
            if (!marked[s]) { 
                dfs(graph, s); 
                // 一次dfs调用就是一个连通分量，第一个连通分量id为0。 
                // 之后分派的id要自增，第二个连通分量的id为1，以词攀类推 
                count++; 
            } 
        } 
    } 
 
    private void dfs(UndiGraph<?> graph, int v) { 
	
			
 1/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