首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2013-12-31
35
问题
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
选项
答案
解法一:采用深度优先遍历方法。算法如下: #define MAX_VERTEX_NUM 20 //最大顶点数为20 typedef struct ArcNode{ //边表结点 int adjvex; //邻接点域 struct ArcNode*nextarc; //指向下一个邻接点的指针域 //若要表示边上信息,则应增加一个数据域info }ArcNode; typedef struct VNode{ //顶点表结点 VertexType data; //顶点域 ArcNode *firstarc; //边表头指针 }VNode,AdjList[MAX_VERTEX_NUM]; //AdjList是邻接表类型 typedef struct{ AdjList adjlist; //邻接表 int vexnum,arcnum; //顶点数和边数 }ALGraph; //ALGraph是以邻接表方式存储的图类型 void DFS(ALGraph G,int V){ ArcNode*p; visited[v]=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 ConnNum1(ALGraph 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); //调用DFS算法 num++: } return(num); } 解法二:采用广度优先遍历方法。算法如下: void BFS(ALGraph G,int v){ ArcNode*p; int Qu[MAX_VERTEX_NUM],front=0,rear=0; //定义循环队列并初始化 int W,i; for(i:0;i<G->n;i++)visited[i]=0; //访问标志数组初始化 prinf("2%d",v); //输出被访问顶点的编号 visited[v]=1; //置已访问标记 rear=(rear+1)%MAX_VERTEX_NUM; Qu[rear]=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<G->n;i++) visited[i]=0; for(i=0;i<G->n;i++) if(visited[i]==0){ BFS(G,i); //调用BFS算法 num++: } return(num); }
解析
转载请注明原文地址:https://jikaoti.com/ti/c9ajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述《国联盟约》的出台背景、主要内容及影响
试分析第二次世界大战的历史地位。
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
1928年2月召开的国民党二届四中全会,规定()为国民政府军政最高机关。
《三家村札记》是由()三位作家共同完成的。
西藏自治区的设立时间是()。
关于荷马时代的叙述,不正确的是()。
规定德国赔款数额最少的是()。
克里特文明的文字类型是()。
明朝中叶,美洲高产的农作物()的传入,对改变当时人们的食品结构产生了重大影响。
随机试题
在ASCⅡ码表中,数字和英文字母按照ASCⅡ码值从小到大排列的顺序为:数字、大写字母、小写字母。()
______determinesagoodmealvariesfromcountrytocountry.
现行规范规定,下列航摄仪参数中,不属于规范要求的检定内容的是()。
某企业年初投资3000万元,10年内等额回收本利,若基准收益率为8%,则每年年末应回收的资金是()。
为了满足多种要求,楼盖基本由三个层次组成,即承重层、面层和()。
位于某市区的房地产开发企业2011年建造商品房一幢,有关费用为:(1)支付地价款200万元。(2)土地征用及拆迁补偿费120万元。(3)前期工程费180万元。(4)基础设施费200万元。(5)建筑安装工程费1500万元。(6)公共配套设施费200万元。(7
结合材料一至五,概述网络媒体在我国民意表达和民主建设中发挥的作用。要求概述简洁全面。300字。依据材料内容,围绕“网络民意对政治民主建设的作用”这一主题写一篇议论文。要求论证有理,论据充分,说服力强。1000字。
2012年上半年浙江省全社会用电同比增长2.0%,增速比一季度回落1.9个百分点。其中,第一产业、第三产业和城乡居民生活的用电增速全面回落,上半年分别增长8.7%、11.3%和13.5%,比一季度分别回落2.8、1.6和1.1个百分点;第二产业用电由一
项目的管理过程用于描述、组织并完成项目工作,而以产品为导向的技术过程则创造项目的产品。因此,项目的管理过程和以产品为导向的技术过程(41)。
情景:你刚刚买了一辆新车,欲把此事告诉你的美国朋友Andy。任务:请你用英语给Andy发一封50个词左右的电子邮件,告诉他:.买车的时间及车的价格;.新车的大致情况和用途;.你对新车的感受。请用下面格式。DearAndy,LiMin
最新回复
(
0
)