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

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

admin2013-12-31  44
问题 设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
选项
答案解法一：采用深度优先遍历方法。算法如下： #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_NUM]； ／／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 ConnNum1(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)； }
解析
转载请注明原文地址:https://kaotiyun.com/show/5vxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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