首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
134
问题
设计一个算法,求无向图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://www.kaotiyun.com/show/yNxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
对中国近代史的起始时间。史学界有不同的看法,请你举出一种观点论述之。(南京大学2012年中国近现代史复试真题)
论述第一次鸦片战争后中国社会经济的变化
论述西汉时期的诸侯王国问题。(2010年统考真题)
抗战以来文艺战线上思想斗争中最重要的问题是()。
郡县制度在春秋战国时代是政治变革中最显著的一个方面,下列选项中,对郡县制度表述错误的是()
我国第一部系统的史学理论著作是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
1543年发表解剖学专著《人体结构论》的是()。
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
随机试题
简述语言和民族文化的相互联系和相互作用。
Thegirl______workwontheprizeistheyoungestinherclass.
A.抑制血管紧张素Ⅱ生成B.抑制血管紧张素与受体结合C.阻止钙离子进入心肌细胞及血管壁平滑肌细胞,使心肌收缩力降低,外周血管扩张D.抑制钠水重吸收,减少血容量,降低心排血量E.减慢心率、降低心排血量,抑制肾素释放美托洛尔降压的作用机制是
患儿,男,6岁。尿少、水肿2天,血压130/90mmHg,尿常规:蛋白(++),红细胞25个/HP,白细胞15个/HP。患儿在入院第2天突然出现头痛、恶心、呕吐、视物模糊,并抽搐1次,此时应考虑出现()
竣工决算的核心内容是()。
某建设工程业主将项目的全部施工任务发包给了甲施工单位,对于这种发承包方式,下列表述中正确的是()。
税收法律关系的产生、变更和消灭是由()决定的。
下面哪些是北美自由贸易区的成员国?()。
(2012河北大学)成数再保险
Womenknowthatalackofsleepleavesthemirritable.However,mostofthem【B1】______thedamageitmaybedoingtotheirskin.
最新回复
(
0
)