假设无向图采用邻接表存储,编写一个算法求连通分量的个数并输出各连通分量的顶点集。
解:以深度优先遍历来求图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的连通分量的个数。对应的算法如下:int visited[ MAXV]; //全局变量数组int DFSTrave( ALGraph * G,int i, int j){ int k, num = 0; // num记录连通分量的个数 for (k = 0;k n;k ++ ) visited[k]= 0; for (k = 0;kn;k t+ ) if ( visited[ i] == o) { num+t ; printf("第出d个连通分量顶点集:", num) ; DFS(G,i) ; //DES是《教程》中的深度优先遍历算法 printf( "\n"); } return num;}说明:本题采用广度优先遍历算法亦可。
举一反三
内容
- 0
n个顶点的无向连通图的连通分量个数为______ 个。
- 1
对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。
- 2
试编写算法判断某无向图是否为连通图,若是非连通图,打印输出连通分量的个数
- 3
设无向图的顶点个数为n，且任何边的两端不是相同顶点，问关于这个无向图的连通分量的数量叙述哪些正确？ A: 至少有1个连通分量 B: 至多有2个连通分量 C: 至少有2个连通分量 D: 至多有n个连通分量
- 4
设无向图的顶点个数为n，且任何边的两端不是相同顶点，问关于这个无向图的连通分量的数量叙述哪些正确？ A: 至少有1个连通分量 B: 至多有2个连通分量 C: 至少有2个连通分量 D: 至多有n个连通分量