首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-26
101
问题
设计一个算法,求无向图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_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
n;i++) visited[i]=0; for(i=0;i
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
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
n;i++) visited[i]=0; for(i=0;i
n;i++) if(visited[i]==0){ BFS(G,i); //调用BFS算法 num++: } return(num); }
解析
本题主要考查图的遍历的应用。对于无向图来说,深度优先遍历或者是广度优先遍历,若无向图是连通图,则一次遍历能够访问到图中的所有顶点,但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器,最后计数器的值即为连通分量个数。
转载请注明原文地址:https://kaotiyun.com/show/zfxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
到19世纪蒸汽时代资本主义取得了具有决定意义的胜利,意思是说()。
以下关于埃赫那吞改革失败的原因,分析不正确的是()
战国时代百家争鸣的局面,是我国学术文化发展的重要阶段,在激烈的争鸣中,有着融合的趋向,下列选项中,不能体现这一特点的是()
新中国建立后发生的一次全局性、长时间的严重“左”倾错误是()。
简述戴高乐独立自主外交政策产生的背景、内容和意义。
以下选项不属于希腊城邦的形成方式和途径的是()。
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
如下图所示为一个带宽为50kbps的卫星信道,它的往返传播延时为500ms。现在有一个网络架设在该信道上,网络使用1000bit长度的帧和停止一等待协议,请回答如下问题:该网络发送一帧的发送延时和传输延时分别是多少?
随机试题
阅读《赵威后问齐使》中的一段文字,回答问题。齐王使使者问赵威后。书未发,威后问使者曰:“岁亦无恙耶民亦无恙耶王亦无恙耶?”使者不说,曰:“臣奉使使威后,令不问王而先问岁与民,岂先贱而后尊贵者乎?”威后曰:“不然苟无岁何以有民?苟无民,何以有君?故
睫状体又称睫状突。
大头瘟的病机是
霍乱与副霍乱的常见表现为
我国保留古代民主传统,实行“禅让”制是在下列哪个时期?()
特朗普制把大班上课、小班讨论和个人独立研究结合在一起,采用灵活的时间单位代替固定的上课时间。
凡年满6周岁的儿童依法入学接受并完成义务教育,条件不具备的地区的儿童可推迟到7周岁。()
有外国友人在社区租房子,晚上十点半以后总举办活动,大声喧哗,吵闹,影响邻居,经了解他们是某大学留学生。你是社区负责人,你怎么办?
已知α1,α2,α3,α4为3维非零列向量,则下列结论:①如果α4不能由α1,α2,α3线性表出,则α1,α2,α3线性相关;②如果α1,α2,α3线性相关,α2,α3,α4线性相关,则α1,α2,α4也线性相关;③如果r(α1,α1+α2,α2+α
HappyBirthdaytoYouThemainproblemindiscussingAmericanpopularcultureisalsooneofitsmaincharacteristics:itw
最新回复
(
0
)