首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-26
103
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
罗马帝国分为东西两部的时间是()。
汉武帝时期,在民族关系上采取了一系列措施,其中不包括()。
在半殖民地半封建社会条件下,由于经济地位决定了在政治上带有两重性的阶级是()。
标志着清政府被迫放弃闭关政策,开始面向世界,基本上完成了从传统的理藩向近代外交转化的事件是1861年()。
简述布匿战争的过程。
明治维新中,事实上废除了封建领主土地所有制的举措是()。
《马可波罗行纪》中载:“此汗八里大城之周围,约有城市二百,位置远近不等,每城皆有商人来此买卖货物,盖此城为商业繁荣之城也。”“此城”指的是()。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
随机试题
评价者根据某一标准将每一名员工与其他员工进行逐一比较,两两比较,并将每一次比较中的优胜者选出。最后,根据每一名员工得胜次数的多少进行排序。这指的是绩效考核方法中的【】
属于CT设备采样系统关键部件的是
整个人体的脏腑组织器官以何为中心
患者,男,35岁。因在操作机器时不慎伤及右手,突然昏厥不省人事.针灸治法为
某安装公司承包一演艺中心的空调工程,演艺中心地处江边(距离江边100M),空调工程设备材料:双工况冷水机组(650Rt)、蓄冰槽、江水源热泵机组、燃气锅炉、低噪声冷却塔(650t/h)、板式热交换机、水泵、空调箱、风机盘管、各类阀门(DN20~DN700)
2016年12月12日,贺某去某小学接8周岁的女儿小贺放学,路过大华商场时,被安装在商场外墙的被风吹落的广告牌砸伤,贺某头部受伤,简单包扎后即赶往学校。小贺在学校门口等待其父亲的同时,捡起路边石块向马路上的车辆扔着玩儿,击中一辆正常行使的出租车,
恩格斯说:“一些小事可以看出一个人的优良品质。”结合公务员的工作特点谈谈体会。
亚述帝国的创建者是公元前8世纪后期的()。
孔子说“三军可夺帅也,匹夫不可夺志也”;墨子说“志不强者智不达”;诸葛亮说“志当存高远”。对当代大学生来说,上述三句话对我们的启示是()
蒸汽、电力和自动纺织机甚至是比巴尔贝斯、拉斯拜尔和布朗基诸位公民更危险万分的革命家。这一论断的含义是()。
最新回复
(
0
)