首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-01-04
21
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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){ //判断n个顶点以邻接表示的有向图g中,顶点vi各vj是否有路径, //有则返回1,否则返回0。 for(i=l;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间无通路 提示:此题考查的知识点是图的遍历。在有向图中,判断顶点Vi和顶点vj间是否有路径,可采用搜索的方法,从顶点vi出发,不论是深度优先搜索(DFS)还是宽度优先搜索(BFS),在未退出DFS函数或BFS函数前,若访问到vi,则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则flag=1。
解析
转载请注明原文地址:https://kaotiyun.com/show/WQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
概述汉代从“黄老之学”到“霸王道杂之”的思想演变。(首都师范大学2013年历史学基础真题)
试论春秋战国时期思想文化获得发展的主要原因。
1891年标志着电机发展新阶段开始的是在电能实际应用中首次采用()。
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
随机试题
引起局麻药中毒的原因是()。
胞浆内可见大量酶原颗粒的细胞是
美国传记作家罗斯·特里尔认为:“万隆时代,对毛泽东在中国之外的形象,是个丰收的时代,因为无数第三世界国家和他的政府建立了关系。在这个时代,毛泽东脚踏两只船。”“脚踏两只”是指()。
根据我国《刑事诉讼法》的规定,人民检察院对于公安机关移送起诉的案件.应当在一个月以内作出决定,重大、复杂的案件可以延长的时间是()。
毛泽东在《<共产党人>发刊词》中所说的“伟大的工程”是指:
2019年6月,全国发行地方政府债券8996亿元,同比增长68.37%,环比增长195.63%。其中,发行一般债券3178亿元,同比减少28.33%,环比增长117.08%,发行专项债券5818亿元,同比增长540.04%,环比
小红装病逃学了一天,大明答应为她保密。事后,知道事情底细的老师对大明说,我和你一样,都认为违背承诺是一件不好的事情。但是,人和人的交往,事实上默认一个承诺,这就是说真话,任何谎言都违背这一承诺。因此,如果小红确实装病逃学,那么,你即使已经承诺为她保密,也应
[*][解法一][解法二]
Likemanyofmygeneration,Ihaveaweaknessforheroworship.Atsomepoint,however,wealltoquestionourheroesandourne
Nosooner______thanherealizedthatheshouldhaveremainedsilent.
最新回复
(
0
)