这篇讲的是连通分量，连通分量是深度优先搜索算法的一个应用。

public class CC    CC(Graph g)      预处理构造函数    boolean connected(int v,in w)  v和w连通吗    int count()     改图中的连通分量个数    int id(int v)   顶点v所在的连通分量编号

具体实现如下：

package Graph;public class CC {    /*     * 计算一个图中的连通分量，从起始点开始进行dfs算法，同时用一个以顶点作为索引的数组id[]来保存该点所在的连通分量的起始点，也就是id     * 这样，判断两个点是否处于同一个连通分量，只要判断id是否相同     */    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 s = 0;s < G.V();s++){            if(!marked[s]){                dfs(G,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;    }}

同样还能解决双色问题，即“能够用两种不同颜色将顶点着色，使得相邻的顶点颜色不同吗？等价于这个图是一个二分图吗？

/* * 使用dfs算法，来判断一个图中的顶点是否可以用两种颜色染色，使得相邻的顶点颜色不同 * 也就是，判断该图是否是一个二分图： * 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 *  */public class TwoColor {    private boolean[] marked;    private boolean[] color;    private boolean isTwoColorable = true;    public TwoColor(Graph G){        marked = new boolean[G.V()];        color = new boolean[G.V()];        for(int s = 0;s < G.V();s++){            if(!marked[s])                dfs(G,s);        }    }    private void dfs(Graph G,int v){        marked[v] = true;        for(int w: G.adj(v)){            if(!marked[w]){                color[w] =!color[v];            }            else if (color[w] == color[v])                isTwoColorable = false;        }    }    public boolean isTwoColorable(){        return isTwoColorable;    }}