问题描述

深度优先搜索的下一个直接应用就是找出一幅图的所有连通分量。“与…连通”是一种等价关系，它能够将所有顶点切分为等价类（连通分量）。

API

连通分量的API：

实现

CC的实现使用了marked[]数组来寻找一个顶点作为每个连通分量中深度优先搜索的起点。递归的深度优先搜索第一次调用的参数是顶点0——它会标记所有与0连通的顶点。然后构造函数中的for循环会查找每个没有被标记的顶点并递归调用dfs()来标记和它相邻的所有顶点。另外它还使用了一个以顶点作为索引的数组id[]，将同一个连通分量中的顶点和连通分量的标识符关联起来（int值）。

代码

其中图用到了Graph
Bag.java：

package section1_3;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;
    private int n;

    private class Node<Item> {
        Item item;
        Node<Item> next;
    }

    public Bag() {
        first = null;
        n = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void add(Item item) {
        Node oldfirst = first;
        first = new Node<>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

CC.java：

package section4_1;

import section1_3.Bag;

public class CC {

    private boolean[] marked;
    private int[] id;
    private int count;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int v = 0;v < G.V();v++) {
            if (!marked[v]) {
                dfs(G,v);
                count++;
            }
        }
    }

    public 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;
    }

    public static void main(String[] args) {
        int[][] data = {
                {0,5},
                {4,3},
                {0,1},
                {9,12},
                {6,4},
                {5,4},
                {0,2},
                {11,12},
                {9,10},
                {0,6},
                {7,8},
                {9,11},
                {5,3}
        };
        int vn = 13;
        int e = 13;
        Graph graph = new Graph(vn,e,data);
        CC cc = new CC(graph);

        int M = cc.count();
        System.out.println(M + " components");

        Bag<Integer>[] components;
        components = (Bag<Integer>[]) new Bag[M];

        for (int i = 0;i < M;i++) {
            components[i] = new Bag<>();
        }

        for (int v = 0;v < graph.V();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();
        }
    }
}