首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
admin
2012-06-21
101
问题
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
选项
答案
解法一:采用深度优先遍历方法。算法如下: Void DFS(AGraph*G,int v) { ArcNode*p; visited[v]=1; //置已访问标记 printf("%d",v);//输出被访问顶点的编号 p=G->adjlist[V].firstarc;//p指向顶点v的第一条边的终结点 while(p!=NULL) . { if(visited[p->adjvex]==0)//若p->adjvex顶点未访问,递归访问它 { DFS(G,p->adivex); p=p->nextarc; //p指向顶点v的下一条边的终结点 } } int ConnNuml(AGraph*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); num++; } } } return(num); } 解法二:采用广度优先遍历算法 void BFS(AGraph G, int v) AreNode*p; int Qu[MAXV],front=0,rear=0 int w,i; for(i=0;i<G->n;i++)visited[i]=0; printf("2%d",v); visited[v]=1; rear=(rear+1)%MAXV; Qu[rear]=v; while(front!=rear) { front=(front+1)%MAXV; w=Qu[front]; p=G->adjlist[w].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf("%2d",p->adjvex); //访问相邻顶点 visited[p->adjvex]=1; rear=(rear+1)%MAXV; //该顶点人队 Qu[rear]=p->adjvex; } p=p->nextarc; //找下一个邻接顶点 } } printf("\\n"); } int ConnNum2(AGraph*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++; } retum(num); }
解析
转载请注明原文地址:https://kaotiyun.com/show/yNxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
我国第一部系统的史学理论著作是()。
在第二次鸦片战争中,英国割占的中国领土是()。
在第二次世界大战后英属印度的各派政治力量中影响最大的是()。
关于荷马时代的叙述,不正确的是()。
标志着南京国民政府在全国范围内形式上完成统一的事件是()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
拉美独立后,各国政治上的一种普遍现象是(),实质上它是拉美各国大地主专政的一种特殊形式。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
下列的网络协议中,()的运输层协议是使用TCP的。
随机试题
用20m长度卷尺丈量距离时,200m长度至少要分()段进行。
在那些不是以民族为基础的古代国家中,国家结构形式一般都实行()
WhenChristopherColumbus"discovered"theNewWorldin1492,hethoughthehadreachedthecontinentofAsiaandhadlandedin
何种分子量的蛋白质完全不能通过肾小球滤过膜
最不适用于成年人颅脑超声检查的探头频率是
慢性闭锁性牙髓炎的临床表现如下,除外A.不定时的自发痛B.热测引起迟缓痛C.洞内探及穿髓孔D.叩诊多有不适感E.有过自发痛病史
配制港航工程混凝土采用()水泥。
按照付息的方式分类,国债可以分为( )。
下列四组地形中,全部属于西部大开发区域的是()
Familiarasitmayseem,gravityremainsamysterytomodernphysics.Despiteseveraldecadesoftrying,scientistshavefailed
最新回复
(
0
)