首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-26
107
问题
设计一个算法,求无向图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_NUM3; //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 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]==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
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
n;i++) visited[i]=0; for(i=0;i
n;i++) if(visited[i]==0){ BFS(G,i); //调用BFS算法 num++: } return(num); }
解析
本题主要考查图的遍历的应用。对于无向图来说,深度优先遍历或者是广度优先遍历,若无向图是连通图,则一次遍历能够访问到图中的所有顶点,但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器,最后计数器的值即为连通分量个数。
转载请注明原文地址:https://kaotiyun.com/show/zfxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
罗马帝国分为东西两部的时间是()。
《马关条约》中最能体现列强对华侵略进入新阶段的内容是()。
马克思第一次明确论述无产阶级历史使命和无产阶级必须与科学理论相结合思想的著作是()。
论述近代西欧海上霸权的更迭
试论述清朝前期是如何巩固统一的多民族国家的?
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
以下()协议完成了从网卡到IP地址的映射。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
随机试题
I’msorry,butIhaveaquestionto______you.
可用于阴血不足,虚热扰心之心烦失眠的方剂是
下列哪项是恶阻肝胃不和的主要表现
A.柴胡疏肝散B.半夏厚朴汤C.丹栀逍遥散D.滋水清肝饮E.甘麦大枣汤治疗心神惑乱型郁证的代表方是
A.以阻塞性通气障碍为主B.以限制性通气障碍为主C.混合性通气功能障碍D.以弥漫性通气障碍为主E.以呼吸中枢功能障碍为主自发性气胸的临床特征是
为使药材色泽洁白,防止霉烂,常在干燥前后较大的根及根茎,坚硬的藤、木类和肉质的果实为便于干燥通常干燥前要
一老年男性患者,近1个月来,感觉头晕、嗜睡、乏力,经血液流变学检查血液黏度增高,血小板黏附和血小板聚集试验值增高,医生诊断为脑血栓前兆,嘱咐患者注意休息、适当运动、多喝水。若患者出现不耐受,可替换药物为
心墙坝或斜墙坝铺筑时应向上游倾斜()的坡度,均质坝应使中部凸起,向上、下游倾斜1%~2%的坡度。
甲公司是一家成立于上世纪90年代初的手机制造商,目前为亚洲地区多个国家和地区的商业、政府、大型机构和个人提供服务。主要产品为普通手机,甲公司通过其“全球计划和直销模式”,以统一的标准向客户提供定制的成套服务和支持,逐步发展成享誉全球的手机品牌,尤其在PC业
计算机中,中央处理器CPU由________和___________两部分组成。
最新回复
(
0
)