请设计一个算法，求出无向图G的连通分量个数？

Question

如题所述

Answer 1

int Connect(AdjGraph *G){//参数为邻接表

        int i,count=0;

        DFC(G,0);//图的深度遍历，以0顶点开始

        for(int i = 0;i<G->n;i++){

            if(visited[i] == 0){//图遍历算法的辅助数组，若为0则没遍历到，说明非连通

                count++;

                DFS(G,i);

        }

    }

        if(count == 0 )//若上面循环遍历完毕count=0则说明改图连通，只有一个连通分量

            count = 1;

            return count;

}