2. 考研
  3. 设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

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

admin2013-07-12  106
问题 设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
选项
答案解法一：采用深度优先遍历方法。算法如下： # define MAX＿VERTEX NUM 20 ／／最大顶点数为20 typedef struct ArcNode{ ／／边表结点 int adjvex； ／／邻接点域 struct ArcNode*nextarc； ／／指向下一个邻接点的指针域 ／／若要表示边上信息，则应增加一个数据域info )ArcNode； tvpedef struct VNode{ ／／顶点表结点 VertexType data： ／／顶点域 ArcNode *firstarc； ／／边表头指针 }VNode，AdjList[MAX VERTEX—NUM]； ／／AdjList是邻接表类型 typedef struct{ AdjList adjlist； ／／邻接表 int veXnulTl．arcnum； ／／顶点数和边数 }ALGraph： ／／ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph G，int V){ ArcNode*P： visitedrv]＝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；in；i＋＋) visited[i]＝0； for(i＝0；in；i＋＋) if(visited[i]＝＝O){ DFS(G，i)； ／／调用DFS算法 num＋＋： } return(num)； } 解法二：采用广度优先遍历方法。算法如下： void BFS(ALGraph G．int V){ ArcNode*P； int Qu[MAX VERTEX＿NUM2，front＝0，rear＝0； ／／定义循环队列并初始化 int w，i； for(i：0；in；i＋＋)visited[i]＝0； ／／访问标志数组初始化 Drinf(“2％d”，v)； ／／输出被访问顶点的编号 visitedrv]＝1； ／／置已访问标记 rear＝(rear＋1)％MAX＿VERTEX＿NUM； QuErear]＝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：in；i＋＋) visited[i]＝0； for(i＝0；in；i＋＋) if(visited[i]＝＝O){ BFS(G，i)； ／／调用BFS算法 num＋＋： return(num)； }
解析 本题主要考查图的遍历的应用。对于无向图来说，深度优先遍历或者是广度优先遍历，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器，最后计数器的值即为连通分量个数。
转载请注明原文地址:https://www.kaotiyun.com/show/1rxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)