首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-01-16
38
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点V
i
到顶点V
j
的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
选项
答案
算法1: int visited[]=0; //全局变量,访问数组初始化 int dfs(AdjList g,vi){ //以邻接表存储的有向图g,判断vi到vj是否有通路,返回1或0 visited[vi]=1; //visited是访问数组,设顶点的信息就是顶点编号 p=g[vi].firstarc; //第一个邻接点 while(p!=null){ j=p一>adjvex; if(vj==j){flag=1;return(1);} //vi和vj有通路 if(visited[j]==0)dfs(g,j); p=p一>next: }//while if(!flag)return(0); } 算法2:输出vi到vj的路径,其思想是用一个栈存放遍历的顶点,遇到顶点vj时输出路径。 void dfs(AdjList g,int i){ //顶点vi和顶点vj问是否有路径,如有,则输出 int top=0,stack[]; //stack是存放顶点编号的栈 visited[i]=1; //visited数组在进入dfs前已初始化 stack[++top]=i; p=g[i].firstarc; //求第一个邻接点 while(p){ if(P一>adjvex==j){ stack[++top]=j; printf(“顶点vi和vj的路径为:\n”); for(i=1;i<=top;i++)printf(“%4d”,stack[i]); exit(0); } else if(visited[p一>adjvex]==0){dfs(g,g一>adjvex);top--;P=p一>next;} } } 算法3:非递归算法求解。 int Judge(AdjList g,int i,j){ //判断13.个顶点以邻接表示的有向图g中,顶点vi各vj是否有路径, //有则返回1,否则返回0。 for(i=1;i<=n;i++)visited[i]=0; //访问标记数组初始化 int stack[],top=0;stack[++top]=vi; while(top>0){ k=stack[top--];p=g[k].firstarc; while(P!=null&&visited[p一>adjvex]==1)P=p->next; //查第k个链表中第一个未访问的弧结点 if(p==null)top--: else{ i=p一>adjvex; if(i==j)return(1); //顶点vi和vj间有路径 else{visited[i]=1;stack[++top]=i;} } }while return(0); }//顶点vi和vj间无通路 提示:此题考查的知识点是图的遍历。在有向图中,判断顶点v
i
和顶点v
j
间是否有路径,可采用搜索的方法,从顶点v
i
出发,不论是深度优先搜索(DFS)还是宽度优先搜索(BFS),在未退出DFS函数或BFS函数前,若访问到v
j
,则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则flag=1。
解析
转载请注明原文地址:https://kaotiyun.com/show/0iRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
罗马帝国疆域扩张到顶点是在()统治时期。
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
洪秀全以宗教手段组织起义,主要利用的是()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
沙俄企图侵占中国东北地区,制造“海兰泡惨案”的时间是()。
南宋书院的复起,是由朱熹开始的。他重建白鹿洞书院,亲自到书院讲学,还亲手制定()。
两宋时期,不同地域曾出现濂、洛、关、阐等学术流派。北宋后期到南宋中期,王安石的新学成为影响最大的学派,这主要是由于()
8世纪中期,控制东自黑龙江,西到阿尔泰山广大地区的民族是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
随机试题
文档标题导航有先决条件,打开的超长文档必须事先设置有________。
镜检可见花粉粒极面观呈三角形,有3副合沟,该药材是
颊肌的起点是
男,55岁,突发持续胸痛4小时。查体:BP110/50mmHg,心率30次/分,律齐,心电图示急性下壁、右室心肌梗死,三度房室传导阻滞。为提高心室率应立即采取的治疗措施是
在监理合同履行过程中,发生不可抗力导致施工被迫中断,不可抗力影响消失后恢复施工前必要的监理准备工作属于()工作。
根据《证券公司从事代办股份转让主办券商业务资格管理办法(试行)》的规定,最近2年不存在重大违法违规行为的证券公司才有资格申请从事代办股份转让服务业务。()
根据《企业破产法》规定,管理人的职权有()。(2015年)
《中共中央关于全面推进依法治国若干重大问题的决定》指出,全面推进依法治国,总目标是()。
海尔总裁张瑞敏曾经说过这样的话,企业要靠无形资产来盘活有形资产,只有先盘活人,才能盘活资产。对这句话,准确的理解是()。
A、Heneedsthemoneybadly.B、Heenjoysusingcomputers.C、Hewantstoworkinthecitycentre.D、Hehasrelevantworkingexperi
最新回复
(
0
)