首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2013-12-31
33
问题
设计一个算法,求无向图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://kaotiyun.com/show/5vxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《关于建国以来党的若干历史问题的决议》对毛泽东和毛泽东思想历史地位的科学评价。
简述《资政新篇》的内容与意义。(安徽师范大学2004年中国近代史真题)
中国无产阶级队伍壮大的重要影响是()。①标志着中国无产阶级登上历史舞台②为共产党的诞生奠定了阶级基础③为中国革命的转变奠定了阶级基础④推动了新文化运动的发展
《洛迦诺公约》规定:德、比、法、英、意相互保证维护《凡尔赛和约》所规定的德法和德比之间的边界现状。在当时条件下这一规定的最大受益国是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
概述日本古代文化的发展情况。
三大战役的先后顺序是()
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
在欧盟发展历史上,促使欧盟正式成立的文件是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
随机试题
()属于全局性战略。
公证书是由国家公证机构根据公民、法人或其他组织的申请,依法出具的有法律效力的证明文件,它具有()
集约型经济增长方式推动经济增长,主要是靠()。
肘关节后脱位是三个骨性标志相互关系发生改变的是
某手表厂机械手表产品中的一个齿轮外径设计尺寸为3.1mm,生产过程中所允许的误差为(﹢0.0015,﹣0.0020)。某道工序承担并完成齿轮外径的加工,现在需要通过随机抽样对该工序的工序能力进行评估,抽取了250个样品,经测算,样本平均值和公差中心重合
在计算披露的经济增加值时,下列各项中,需要进行调整的项目有()。
年代为距今6800—3500年,包含有仰韶文化、龙山文化、商代文化三个不同历史时期内容的古文化遗址是()。
甲、乙两个工人加工一批零件,若甲、乙单独完成,甲比乙多用5天,若甲、乙两人合作,6天可以完成.若两人合作6天完成后,收到加工费用5000元,求甲、乙两人分别可得多少钱?
邓小平的“建设有中国特色的社会主义理论”这一概念是在党的十四大上提出的。()
"LiteratureClass"Accordingtotheprofessor,whatkindofbookisGulliver’sTravels?
最新回复
(
0
)