首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
106
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
1945年2月的雅尔塔会议决定以()方式处理战败的德国。
19世纪三四十年代,欧洲无产阶级作为独立的政治力量登上政治历史舞台的历史条件包括()。①资本主义制度的全面确立②科学社会主义诞生③资本主义经济危机的发生④工业革命使社会日益分裂为两大阵营
马克思指出:“鸦片不曾产生催眠的作用,而倒产生了惊醒作用,历史的发展好像首先要麻醉这个国家的人民,然后才可能把他们从历来的麻木状态唤醒似的。”这里所说的“唤醒”的意思是()。
连续五期用全部或大部分的篇幅报道和评论了五四运动这一伟大运动的杂志是()。
列宁在()中系统地阐明了马克思主义的国家学说。
在第二次鸦片战争中,英国割占的中国领土是()。
桌上有一空盘,只允许放入一个水果。爸爸专向盘中放苹果,妈妈专向盘中放橘子,女儿专等着吃盘中的苹果,儿子专等着吃盘中的橘子。试用P,V原语实现爸爸、妈妈、儿子和女儿间能同步的程序。
操作系统采用页式存储管理方法,要求()。
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。
随机试题
A.Thanks,DaddyB.I’mproudofyouC.Youcan’tbelieveitD.CongratulationsE.Whatmakesthed
关于全麻药体内过程的叙述,正确的是:
全科医生若要充分了解患者的问题必须要做到
不属于Ⅱ型变态反应的是
我国最早注意病案的记录的医家为
有一宗房产交易,成交价格为3000元/m2,付款方式是首付10%,余款在1年内按月等额付清,假设月利率为0.5%,其一次支付的实际成交价格为()。
位于北京市的某房地产开发企业,2014年发生相关业务如下:(1)1月份购买一宗8000平方米的土地,合同上注明的土地价款是10000万元,缴纳相关税费400万元,已经取得土地使用证。2月份对该土地进行“三通一平”,与建筑公司签订的合同上注明工程费
销售预测的德尔菲法属于()。
幼儿词汇的发展表现在词类范围的日益扩大,儿童掌握词汇的顺序为()。
ThedivorcerateinAmericaisabout______.Americanmothersgobacktoworkbecause______.
最新回复
(
0
)