图论算法——无向图的连通分量

　

连通分量

引言

深度优先搜索的一个直接应用就是找出一幅图的所有连通分量。

在深度优先搜索的递归调用期间，只要是某个顶点的可达顶点都能在一次递归调用期间访问到。

有关图的概念可参考博文数据结构之图的概述

连通分量

连通分量：不连通的图是由2个或者2个以上的连通子图组成的。这些不相交的连通子图称为图的连通分量。

比如下图中有四个连通分量

代码

通过id[]标识连通分量，同一连通分量的count值相同,count初始化为0。

for (int s = 0; s < g.vertexNum(); s++) {
   if (!marked[s]) {
        //s的一次递归调用能访问所有与它连通的顶点
        dfs(g,s);
        //到这里说明s的连通顶点已经访问完毕
        count++;
    }
}

实现如下：

package com.algorithms.graph;

import com.algorithms.queue.Queue;

/**
 * 计算无向图的连通分量
 * @author yjw
 * @date 2019/5/22/022
 */
public class CC {
    private boolean[] marked;
    /**
     * 标识连通分量，同一连通分量的值相同
     * 0：第一个连通分量
     * 1：第二个连通分量
     * ...
     *
     * 值为0到count - 1之间
     */
    private int[] id;
    /**
     * 连通分量数
     */
    private int count;

    public CC(Graph g) {
        marked = new boolean[g.vertexNum()];
        id = new int[g.vertexNum()];
        for (int s = 0; s < g.vertexNum(); s++) {
            if (!marked[s]) {
                //s的一次递归调用能访问所有与它连通的顶点
                dfs(g,s);
                //到这里说明s的连通顶点已经访问完毕
                count++;
            }
        }
    }

    private void dfs(Graph g,int v) {
        marked[v] = true;
        id[v] = count;//标识连通分量
        for (int w: g.adj(v)) {
            if (!marked[w]) {
                dfs(g,w);
            }
        }
    }

    public boolean connected(int v,int w) {
        return id[v] == id[w];
    }

    public int id(int v) {
        return id[v];
    }

    public int count() {
        return count;
    }

    @SuppressWarnings("unchecked")
    public void print() {
        System.out.println(count + " components");//count个连通分量

        Queue<integer>[]components = (Queue<Integer>[]) new Queue[count];
        for (int i = 0; i < components.length; i++) {
            components[i] = new Queue<>();
        }


        for (int i = 0; i < id.length; i++) {
            components[id(i)].enqueue(i);
        }
        for (Queue<Integer> queue : components) {
            System.out.println(queue);
        }

    }

    public static void main(String[] args) {
        Graph g = new Graph(10);
        g.addDiEdges(0,1,2);
        g.addDiEdges(4,5,6);
        g.addEdge(5,7);
        g.addEdge(8,9);

        //System.out.println(g);
        CC cc = new CC(g);
        cc.print();
    }
}

其中Queue和Stack的实现见 栈和队列的实现

我们对示例图计算连通分量，得到输出:

4 components
[0 1 2]
[3]
[4 5 6 7]
[8 9]

文章最后发布于: 2019-05-22 19:19:37

相关阅读

Happy Tree Friends（图论）

题目描述There is a Happy Tree on an island. Happy Tree consists of n apples linked by n-1 branches and the No.1 apple is

网站连通率为0的前因后果及预防补救措施

第四步：抓取成功后，也不能说就万事大吉了，还要点击”抓取成功”进去注意：提交网址、抓取网址、抓取UA、网站ip、下载时长、

算法讲解：二分图匹配【图论】

二分图匹配，自然要先从定义入手，那么二分图是什么呢？ 二分图： 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如

企业分公司与总部之间的网络连通高效方案

一、行业背景及现状 当企业发展到一定规模后，为了继续壮大其业务范围，经常需要在不同地区开设分支机构如分公司或者办事处等等,随之

图像连通域分析

转自：https://blog.csdn.net/tiandijun/article/details/51279643，转载仅为方便学习。一、前言二值图像的图像的亮度值只有两个状态