首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-26
85
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
德、意两个法西斯国家领土连成一片是在()事件之后。
波兹南事件后,()出任波党第一书记。
20年代国际关系的中心是()。
魏晋南北朝时期道家得到了迅速发展,援儒入道,在道教官方化过程中有重大贡献的北朝人物是()。
关于明朝“缇骑”的叙述,不正确的是()
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
在某个操作系统中,通过大量的实验,人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比,即可用内存加倍,缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns,但若发生了缺页中断就需要1ms。一个程序运行了60s,期
随机试题
下列属于随机抽样的是()
除了哪一种化合物外,下列化合物都含有高能键
患者,男,55岁。昨天中午参加婚宴后下午开始腹痛,为持续性胀痛,牵涉到后背,伴恶心、呕吐。有胆囊结石病10年。查体:体温37.2℃,血压110/82mmHg,脉率108次/分,呼吸24次/分,巩膜可疑黄染,上腹膨隆,全腹压痛,以左上腹为重,轻度肌紧张,肠鸣
钢管混凝土施工质量的检测方法为()。
下列经济业务会引起负债减少的是()。
下列属于金融租赁的优势的有()。
事业单位的事业结余和经营结余均应在期末转入非财政补助结余分配。()
起草单项工资制度的程序包括()。
按照规划,2020年我国新能源(包括可再生能源)在总能耗中的比例是15%,石油、煤炭等不可再生的传统能源比例仍达85%。在此背景下,“节能提效”被提到了我国发展低碳经济的首选位置上。低碳经济是以低能耗、低污染、低排放为基础的一个经济模式,包含能源的高效利
下图是网络地址转换NAT的一个示例图中①和②是转换前后的地址,它们依次应为()。
最新回复
(
0
)