首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
114
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
下列各项中,《凡尔赛和约》没有做出最后规定的是()。
19世纪末的中国成为列强争夺的焦点,列强掀起了瓜分中国的狂潮。其中法国把()变成了自己的势力范围
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
以下关于玛雅文明叙述,不正确的是()。
分析近代西欧在世界产生重大影响的优势。(江西师范大学2013年世界通史真题)
11世纪中叶,一批激进的克吕尼派修士强调教皇的至高无上的地位,在全西欧范围内向世俗政权、向国王进攻,这就是所谓的()。
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
随机试题
神经电生理检查发现F波异常,提示
流行病学中的偏倚分为()。
某工厂扩建项目需建设二期厂房,建设单位将一期建设时的勘察成果提供给设计单位,在建设单位一再坚持下,设计单位完成了设计文件。工程竣工验收时,发现由于设计文件对厂房基础处理不当而引起厂房不均匀沉陷,对此造成的损失应由()分摊。
(1)账套信息账套编码:009;账套名称:E公司;采用默认账套路径;启用会计期:2009年1月;会计期间设置:1月1日至12月31日。(2)单位信息单位名称:E公司。(3)核算类型该企业的记账本位币:人民币;企业类型:工业;行业性质:新会计制度科
2001年5月份赵某与其他三人共同进行一项装修活动,共取得装修费42000元,因该装修活动最先为赵某承揽,因此按协议赵某应得2000元承揽费,其余四人平分。另外,本月赵某在一次有奖销售中中奖,奖品为价值2000元的洗衣机。根据以上资料回答下列问题:
住房公积金的资金来源为()。
某企业年初未分配利润借方余额为100万元,本年实现净利润500万元,经股东大会批准,该公司按10%提取法定盈余公积,按5%提取任意盈余公积,则该企业年末可供投资者分配的分利润()万元。
人们通过观察别人的行为和活动,以相同的方式做出反应的能力称之为()
Peter,whomeveryonesuspected,______tobeinnocent.
Engineeringstudentsaresupposedtobeexamplesofpracticalityandrationality,butwhenitcomestomycollegeeducationIam
最新回复
(
0
)