首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-26
102
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
《马关条约》中最能体现列强对华侵略进入新阶段的内容是()。
三国时期,三国称帝的先后顺序是()。
简述布匿战争的过程。
简述当代科技革命发生的背景条件。
下列关于胡司战争的叙述错误的一项是()。
俄罗斯的私有化进程始于()年。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
随机试题
某村村民吴某因家里人口多,住房紧张,向乡政府提出建房申请。经乡人民政府土地管理员刘某批准后,即开始划线动工。周围左邻申某与右邻崔某发现吴某占用了自己使用多年的宅基地,即同吴某交涉。吴某申辩说建房是按批准文件划线动工,不同意改变施工计划。如申某与崔某申请
下列变化中不属于中性粒细胞毒性变化的是
某鸡场1500只240N龄罗曼蛋鸡发病,产蛋率下降。少数鸡精神沉郁,每隔2~3天有个别鸡死亡,病死鸡皮下脂肪多,腹腔内有大量脂肪沉积,充满血样液体,肝肿大,包膜破裂、质松软易碎、有油腻感。该病最有效的治疗药物是()
根据形成苷键的原子分类,属于s-苷的是
下列楼板平面布置图中,建筑形体平面规则的是()。
下列关于货币现值和终值的说法中,正确的有()。
被称为“第二代基因工程”的是()。
[A]star[B]ticket[C]creditcard[D]piano[E]restaurant[F]beer[G]umbrella
Whendoestheplanetakeoff?WhichpartofthefactorydoesAlanwanttochange?
WorkisaveryimportantpartoflifeintheUnitedStates.WhentheearlyProtestant【1】cametothiscountry,theybroughtthe【
最新回复
(
0
)