首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
115
问题
设计一个算法,求无向图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月的雅尔塔会议决定以()方式处理战败的德国。
20世纪30年代的国联的所作所为,反映的实质问题是国联()
1516年,法国国王同教皇签订了协约,规定法王有权任命本国教会的高级神职,有权向教士征税,该协约是()。
蒙古军西征之后,罗斯处于()的控制之下。
下列对春秋时期各国称霸的顺序描述错误的选项是()
东欧国家的私有化方式一般有四种,其中波兰采取的主要方式是()
阅读下列材料,结合所学知识回答问题:材料一16—17世纪西欧医生的地位还很低,尽管主要的宫廷医生有很高的经济收入,但医生并不被认为是一个很光荣的职业,直到17世纪中叶,一位绅士还拒绝同一位有钱的医生的女儿结婚。律师职业虽然不被视为低等,
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指令格式为RS型指令,其中“sU
随机试题
通过减少脑组织中的水分降低颅内压的治疗方法是
用下列何种方法检测HCG可免除黄体生成素的干扰
(一)资料2014年3月,某审计组对乙公司2013年度财务收支情况进行了审计。乙公司主要从事钢材产品的加工和贸易业务。有关审计的情况和资料如下:1.为了检查乙公司生产和存货业务循环内部控制的有效性,审计组准备实施如下审计程序:①检查生产
【2015年陕西渭南.单选】古代思想家王守仁曾指出,夫学贵得之心,求之于心而非也,虽其言之出于孔子.不敢以为是也……求之于心而是也,虽其言之出于庸常,不敢以为非也。他主要强调的是()。
纵观现代化历程,中国改革一直是在争论中推进的,之所以能够顺利推进并取得举世瞩目的成就,就是因为主流意识形态具有强大的_________力量,总是能够超越左与右,促使社会形成新的共识。而主流意识形态有这样强大的力量,恰恰是从不同社会思潮中汲取智慧,而不是__
下列哪个测验是利用效标团体法编制的
1956年党的八大指出我国社会的主要矛盾是()
设f(x)与g(x)在(一∞,+∞)上皆可导,且f(x)<g(x),则必有
下列关于栈和队列的描述中,正确的是()。
Weallknowthatscienceplaysanimportantroleinthesocietiesinwhichwelive.Manypeoplebelieve,however,thatourprogr
最新回复
(
0
)