设计一个算法 求无向图G（采用邻接表存储)的连通分量个数。

正确答案：解法一：采用深度优先遍历方法。算法如下： #define MAX_VERTEX_NUM 20 　 ／／最大顶点数为20 typedef struct ArcNode{ 　　 　／／边表结点 　　　　 int adjvex； 　　　　 　／／邻接点域 　　　　 struct ArcNode*nextarc； ／／指向下一个邻接点的指针域 　　　　　　　　　　　　　　　　　 　／／若要表示边上信息则应增加一个数据域info }ArcNode； typedef struct VNode{ 　　　 ／／顶点表结点 　　　　 VertexType data； 　　 　／／顶点域 　　　　 ArcNode *firstarc； ／／边表头指针 }VNodeAdjList[MAX_VERTEX_NUM3； ／／AdjList是邻接表类型 typedef struct{ 　　　　　 AdjList adjlist； 　　　　　／／邻接表 　　　　　 int vexnumarcnum； 　　　 ／／顶点数和边数 }ALGraph； 　　　　　　　　　　　 　／／ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph Gint v){ 　　　　 ArcNode*P： 　　　　 visited[v]=1； 　　　　　　 ／／置已访问标记 　　　　 prinf(”％d”v)； 　　　　 ／／输出被访问顶点的编号 　　　　 P=G－>adjlist[v]．firstarc； ／／p指向顶点v的第一条边的终结点 　　　　 while(p!=NULL){ 　　　　　　 if(visited[p一>adjvex]==0) ／／若p一>adjvex顶点未访问递归访问它 　　　　　　　　 DFS(GP一>adjvex)； 　　　　　　 p=p－>nextarc； 　　　　／／p指向顶点v的下一条边的终结点 } } int ConnNuml(ALGraph G){ 　　　　　　　　／／求图G的连通分量 int inum=0； for(i=0；i<G一>n；i++) visited[i]=0； for(i=0；i<G一>n；i++) if(visited[i]==0){ DFS(Gi)； 　　　　　　　　　　　　　／／调用DFS算法 num++； } return(num)； } 解法二：采用广度优先遍历方法。算法如下： void BFS(ALGraph Gint v){ ArcNode*p； int Qu[MAX VERTEX_NUM]front=0rear=0； ／／定义循环队列并初始化 int wi； for(i=0；i<G一>n；i++) visited[i]=0； 　／／访问标志数组初始化 prinf(”2％d”v)； 　　　 　／／输出被访问顶点的编号 visited[v]=1； 　　　　　　　 ／／置已访问标记 rear=(rear+1)％MAx_VERTEX NUM； Qu[rear]=v； 　　　　　　　　 ／／v入队 while(front!=rear){ 　　　　　 ／／若队列不空时循环 front=(front+1)％MAX_VERTEX_NUM； w=Qu[front]； 　　　　　　　 　／／出队并赋予w P=G一>adjlist[w]．firstarc； ／／找与顶点W邻接的第一个顶点 while(p!=NULL){ if(visited[p一>adjvex]：=0){ ／／若当前邻接顶点未被访问 printf(”％2d”P一>adjvex)； ／／访问相邻顶点 visited[p一>adjvex]=1； 　　　 ／／置该顶点已被访问的标志 rear=(rear+1)％MAx_VERTEX_NUM；　 ／／该顶点入队 Qu rear]=P－>adjvex； } p=p->nextarc； 　　　　　　 　／／找下一个邻接顶点 } } printf(”＼n”)； } int ConnNum2(ALGraph G){ ／／求图G的连通分量 int inum=0； for(i=0；i<G一>n；i++) visited[i]=0； for(i=0；i<G一>n；i++) if(visited[i]==0){ BFS(Gi)； ／／调用BFS算法 num++： } return(num)； }
解法一：采用深度优先遍历方法。算法如下： #define MAX_VERTEX_NUM 20 　 ／／最大顶点数为20 typedef struct ArcNode{ 　　 　／／边表结点 　　　　 int adjvex； 　　　　 　／／邻接点域 　　　　 struct ArcNode*nextarc； ／／指向下一个邻接点的指针域 　　　　　　　　　　　　　　　　　 　／／若要表示边上信息，则应增加一个数据域info }ArcNode； typedef struct VNode{ 　　　 ／／顶点表结点 　　　　 VertexType data； 　　 　／／顶点域 　　　　 ArcNode *firstarc； ／／边表头指针 }VNode，AdjList[MAX_VERTEX_NUM3； ／／AdjList是邻接表类型 typedef struct{ 　　　　　 AdjList adjlist； 　　　　　／／邻接表 　　　　　 int vexnum，arcnum； 　　　 ／／顶点数和边数 }ALGraph； 　　　　　　　　　　　 　／／ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph G，int v){ 　　　　 ArcNode*P： 　　　　 visited[v]=1； 　　　　　　 ／／置已访问标记 　　　　 prinf(”％d”，v)； 　　　　 ／／输出被访问顶点的编号 　　　　 P=G－>adjlist[v]．firstarc； ／／p指向顶点v的第一条边的终结点 　　　　 while(p!=NULL){ 　　　　　　 if(visited[p一>adjvex]==0) ／／若p一>adjvex顶点未访问，递归访问它 　　　　　　　　 DFS(G，P一>adjvex)； 　　　　　　 p=p－>nextarc； 　　　　／／p指向顶点v的下一条边的终结点 } } int ConnNuml(ALGraph G){ 　　　　　　　　／／求图G的连通分量 int i，num=0； for(i=0；i<G一>n；i++) visited[i]=0； for(i=0；i<G一>n；i++) if(visited[i]==0){ DFS(G，i)； 　　　　　　　　　　　　　／／调用DFS算法 num++； } return(num)； } 解法二：采用广度优先遍历方法。算法如下： void BFS(ALGraph G，int v){ ArcNode*p； int Qu[MAX VERTEX_NUM]，front=0，rear=0； ／／定义循环队列并初始化 int w，i； for(i=0；i<G一>n；i++) visited[i]=0； 　／／访问标志数组初始化 prinf(”2％d”，v)； 　　　 　／／输出被访问顶点的编号 visited[v]=1； 　　　　　　　 ／／置已访问标记 rear=(rear+1)％MAx_VERTEX NUM； Qu[rear]=v； 　　　　　　　　 ／／v入队 while(front!=rear){ 　　　　　 ／／若队列不空时循环 front=(front+1)％MAX_VERTEX_NUM； w=Qu[front]； 　　　　　　　 　／／出队并赋予w P=G一>adjlist[w]．firstarc； ／／找与顶点W邻接的第一个顶点 while(p!=NULL){ if(visited[p一>adjvex]：=0){ ／／若当前邻接顶点未被访问 printf(”％2d”，P一>adjvex)； ／／访问相邻顶点 visited[p一>adjvex]=1； 　　　 ／／置该顶点已被访问的标志 rear=(rear+1)％MAx_VERTEX_NUM；　 ／／该顶点入队 Qu rear]=P－>adjvex； } p=p->nextarc； 　　　　　　 　／／找下一个邻接顶点 } } printf(”＼n”)； } int ConnNum2(ALGraph G){ ／／求图G的连通分量 int i，num=0； for(i=0；i<G一>n；i++) visited[i]=0； for(i=0；i<G一>n；i++) if(visited[i]==0){ BFS(G，i)； ／／调用BFS算法 num++： } return(num)； } 解析：本题主要考查图的遍历的应用。对于无向图来说，深度优先遍历或者是广度优先遍历，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器，最后计数器的值即为连通分量个数。