算法4.3使用深度优先搜索找出图中的所有连通分量

***《算法》笔记导航

《算法》中文第四版P349
2020.8.21
@Stream_

`public class CC`

深度优先搜索的其中一个应用就是找出一幅图的所有连通分量（哪些顶点互相相连）
算法4.1使用深度优先搜索查找图中的路径
算法4.0.1无向图邻接表
算法1.5union-find算法实现（加权quick-union算法）

一、变量，方法，类及其作用

1.变量

private boolean[] marked;
是否检测过和它连通的顶点
private int[] id;
连通分量：以一个编号来表明哪些顶点是互相相连的，一共有多少个不互相相连的图
private int count;
连通分量

2.方法

2.1构造方法

public CC(Graph G)
分配数组大小，对每一个顶点都调用一次dfs检测一次，使每个连通图都可以被检测到

2.2深搜方法

private void dfs(Graph G,int v)
算法4.1使用深度优先搜索查找图中的路径

2.3用于获取返回值的方法

public boolean connected(int v,int w)
检测顶点v和顶点w是否连通（连通分量是否相同）
public int id(int v)
返回顶点v的连通分量标号
public int count()
检测有几个连通图（连通分量的大小）

二、算法的实现

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

三、算法的使用

1.main方法

public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Graph graph=new Graph(sc);

        CC cc=new CC(graph);

        System.out.println("连通分量共有："+cc.count()+" 个");
        for(int i=0;i< cc.count();i++){
            System.out.println("连通分量 "+i+" :");
            for(int j=0;j<graph.V();j++){
                if(cc.id(j)==i){
                    System.out.print(j+" ");
                }
            }
            System.out.println();
        }
    }

2.输入的数据

3.输出的结果

连通分量共有：3 个
连通分量 0 :
0 1 2 3 4 5 6 
连通分量 1 :
7 8 
连通分量 2 :
9 10 11 12

四、算法的优劣、注意和使用场景

检测连通性问题时，实际上union-find算法更快（算法1.5union-find算法实现（加权quick-union算法））因为它不需要完整地构造并表示一幅图
深度优先搜索更适合实现图的抽象数据类型
union find算法适合：只需要判断连通性或是需要完成有大量连通性查询和插入操作混合等类似的任务

算法4.1使用深度优先搜索查找图中的路径
算法4.0.1无向图邻接表
（算法1.5union-find算法实现（加权quick-union算法）
《算法》笔记导航
渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载