圖論算法——無向圖的連通分量

引言

深度優先搜尋的一個直接應用就是找出一幅圖的所有連通分量。

在深度優先搜尋的遞歸調用期間，隻要是某個頂點的可達頂點都能在一次遞歸調用期間通路到。

有關圖的概念可參考博文資料結構之圖的概述

連通分量

連通分量：不連通的圖是由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();
    }
}      

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