首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2013-07-12
48
问题
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
选项
答案
解法一:采用深度优先遍历方法。算法如下: # define MAX_VERTEX NUM 20 //最大顶点数为20 typedef struct ArcNode{ //边表结点 int adjvex; //邻接点域 struct ArcNode*nextarc; //指向下一个邻接点的指针域 //若要表示边上信息,则应增加一个数据域info )ArcNode; tvpedef struct VNode{ //顶点表结点 VertexType data: //顶点域 ArcNode *firstarc; //边表头指针 }VNode,AdjList[MAX VERTEX—NUM]; //AdjList是邻接表类型 typedef struct{ AdjList adjlist; //邻接表 int veXnulTl.arcnum; //顶点数和边数 }ALGraph: //ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph G,int V){ ArcNode*P: visitedrv]=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]==O){ DFS(G,i); //调用DFS算法 num++: } return(num); } 解法二:采用广度优先遍历方法。算法如下: void BFS(ALGraph G.int V){ ArcNode*P; int Qu[MAX VERTEX_NUM2,front=0,rear=0; //定义循环队列并初始化 int w,i; for(i:0;i
n;i++)visited[i]=0; //访问标志数组初始化 Drinf(“2%d”,v); //输出被访问顶点的编号 visitedrv]=1; //置已访问标记 rear=(rear+1)%MAX_VERTEX_NUM; QuErear]=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]==O){ BFS(G,i); //调用BFS算法 num++: return(num); }
解析
本题主要考查图的遍历的应用。对于无向图来说,深度优先遍历或者是广度优先遍历,若无向图是连通图,则一次遍历能够访问到图中的所有顶点,但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器,最后计数器的值即为连通分量个数。
转载请注明原文地址:https://kaotiyun.com/show/1rxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
氏族公社形成的条件和基本标志是()。
德国法西斯能够通过合法方式夺取政权,主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党
论述中国古代历史上北方少数民族南进的周期性原因及其影响。(南开大学2014年中国历史真题)
我国发明生铁冶炼技术是在()。
1543年,发表了解剖学专著《人体结构》的是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
PowerPoint中系统默认的视图模式是()
Crohn病侵犯肠道的深度为
男50岁,患糖尿病13年,近日并发肺炎。查:心率110次/分,血压12/8kPa(90/60mmHg),呼吸35次/分,呼出气有丙酮味,意识模糊。尿酮体强阳性,血糖27.75mmol/L(500mg/dl)。应选用的药是
长期股权投资采用权益法核算时,初始投资成本大于应享有被投资单位可辨认净资产公允价值份额之间的差额,正确的会计处理是()。
公安机关是人民民主专政的工具,关系着国家安危和社会稳定,只有在党的正确领导下才能正确发挥其职能作用。( )
Ad.AEmbassyVacationResortsCalifornia,FloridaandHawaiiAttheEmbassyVacation
-1/6
一个字符的标准ASCII码的长度是()。
计算机的内存储器与外存储器相比较
—Hello,Alice.You______veryhappy.—Yes.Iamhappy.MyparentsarecomingtoseeMetomorrow.
最新回复
(
0
)