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

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

admin2012-06-21  84
问题 设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
选项
答案解法一：采用深度优先遍历方法。算法如下： Void DFS(AGraph*G，int v) { ArcNode*p； visited[v]=1； ／／置已访问标记 printf("％d"，v)；／／输出被访问顶点的编号 p=G-＞adjlist[V]．firstarc；／／p指向顶点v的第一条边的终结点 while(p!=NULL) ． { if(visited[p-＞adjvex]==0)／／若p-＞adjvex顶点未访问，递归访问它 { DFS(G，p-＞adivex)； p=p-＞nextarc； ／／p指向顶点v的下一条边的终结点 } } int ConnNuml(AGraph*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)； num++； } } } return(num)； } 解法二：采用广度优先遍历算法 void BFS(AGraph G， int v) AreNode*p； int Qu[MAXV]，front=0，rear=0 int w，i； for(i=0；i＜G-＞n；i++)visited[i]=0； printf("2％d"，v)； visited[v]=1； rear=(rear+1)％MAXV； Qu[rear]=v； while(front!=rear) { front=(front+1)％MAXV； w=Qu[front]； p=G-＞adjlist[w]．firstarc； while(p!=NULL) { if(visited[p-＞adjvex]==0) { printf("％2d"，p-＞adjvex)； ／／访问相邻顶点 visited[p-＞adjvex]=1； rear=(rear+1)％MAXV； ／／该顶点人队 Qu[rear]=p-＞adjvex； } p=p-＞nextarc； ／／找下一个邻接顶点 } } printf("＼＼n")； } int ConnNum2(AGraph*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++； } retum(num)； }
解析
转载请注明原文地址:https://kaotiyun.com/show/yNxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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