首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2013-12-31
30
问题
设计一个算法,求无向图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
学硕统考专业
相关试题推荐
简述近代香港问题的形成。
分析英、法、美三国资产阶级革命的特点。
分析美国独立战争和南北战争的异同。
中国共产党领导的抗日根据地建立的政权是()。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
晚清时期下列武装力量出现的先后顺序是
七七事变爆发后,()给中国以巨大的支援,双方签订了(),在政治上给中国以重大支持。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
随机试题
代谢性酸中毒在没有发展到循环衰竭程度时,首选治疗应该是
韩国的茶道分为煮茶法和点茶法。
A两性霉素BB氟胞嘧啶C灰黄霉素D利巴韦林E齐多夫定抑制病毒的三磷酸鸟苷合成,抑制病毒mRNA合成的是
下列各键中,不能完成翻页功能的键是()。
MRP的输出文件是()。
正确处理党的领导与政府领导的关系,应遵循()的原则。
以一国为中心、以多国为中心和以全球为中心的人员配备政策各有哪些主要优缺点?它们在何时适用?
中国共产党领导的多党合作和政治协商制度是中国特色社会主义的政党制度,也是我国的一项基本政治制度。这项制度是马克思主义政党理论和统一战线学说与我国具体实际相结合的产物,是我国社会主义民主政治制度的重要组成部分。关于我国的政党制度,下列说法中正确的有(
以下叙述中正确的是
Icouldtellhewassurprisedfromthe______onhisface.
最新回复
(
0
)