首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
53
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
下面属于城市市民的文学作品的是()。
下列选项中,()不是共产党抗日民族统一战线的土地政策的三条基本原则之一。
“莱茵联邦”的建立是在第()次反法联盟之后。
简述清代秘密立储制的操作并作出评价。
魏晋南北朝的手工业技术有所进步,下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
西汉的主要赋税形式中。征收对象是儿童的是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
随机试题
对Graves病甲亢采用甲状腺次全切除术治疗,正确的是
正线轨道有条件时,特大桥、大桥及长度大于1000m的隧道内,宜采用()。
安全检查的重点是查违章指挥和( )。
根据总账与明细账的平行登记要求,每项经济业务发生后,必须在同一天登记总账和明细账。()[2007年真题]
下列各项申,应按照“销售服务——生活服务”税目计缴增值税的是()。
2018年1月,甲、乙、丙出资设立一个普通合伙企业。2021年4月,甲因车祸去世,其妻子戊为唯一继承人。合伙协议对合伙人资格的取得或者丧失未作约定。根据合伙企业法律制度的规定,下列选项中,正确的是()。
《能源生产和消费革命战略(2016—2030)》提出,到2020年将我国能源消费总量控制在()亿吨标准煤以内。
读下图,完成下面各题。导致图中城镇地理位置变迁的重要原因是()。
《雪绒花》是哪一部美国音乐故事片中的一首插曲?()
在窗体上画一个命令按钮,然后编写如下事件过程:PrivateSubCommand1_Click()Dima(5)AsStringFori=1T05a(i)=Chr(Asc("A"
最新回复
(
0
)