首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-01-04
68
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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
学硕统考专业
相关试题推荐
简述维新思想的主要内容及特点。
以下不是巴黎和会的主要议题的是()
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
武昌起义后,全国革命形势发展的同时也潜伏着失败的危机,这主要是由于()。
中国封建社会后期的第一个启蒙学派是由王艮开创的()。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
随机试题
流浪乞讨人员张某到某市甲救助管理站要求提供返乡车票。该站通过查询,发现张某数小时前从该市乙救助管理站获得过返乡车票,决定对其不予救助,甲救助管理站做出此决定的理由是()。
假设你是一家电脑公司的总经理,将于2003年12月25日主持一次年度工作总结会。起草一份会议通知。
电视广告的特点有()
DuringtheOlympicGames,peoplefromallovertheworldcometogetherinpeaceandfriendship.ThefirstOlympicGamesthatwe
具重镇安神作用的药物有
有关磺胺嘧啶银的描述。错误的是
现代投资理论兴起后,学术分析流派投资分析的哲学基础是()。
非银行公众向中央银行出售债券1万元,将所得钞票存入商业银行,央行________1万元,商业银行________1万元。()[中国人民大学2017金融硕士]
=_______.
Worldwidethereareprobably70to100sharkattacksannuallyresultinginabout5to15deaths.Wesay"probably"becausenota
最新回复
(
0
)