首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-01-04
23
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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
学硕统考专业
相关试题推荐
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
1962年初,中共召开了中央工作会议,即“七千人大会”,其议题主要是()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
下列不是苏俄实行战时共产主义政策原因的是()。
文艺复兴运动兴起的时间是()。
在下列哪个条约中,最先出现了片面最惠国待遇()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
已知有向图G=(V,A),其中V={a,b,c,d,e),A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是()。
随机试题
关于消防车道的设计要求,错误的是()。
根据《建筑中水设计规范》(GB50336—2002)规定,中水原水量的计算相当于按照中水水源的()确定。
措施项目清单的编制依据包括()。
指数型ETF采用指数化投资策略,受托人需时常调整股票组合。( )
甲公司是从事商品批发业务的商业企业,2014年甲公司欲对乙公司进行收购(采用购股方式),根据预测分析,并购前乙公司2014~2017年的独立的自由现金流量依次为一100万元,200万元,250万元,350万元。并购后较之并购前新增的自由现金净流量依次为50
下列股利政策中,适合于成熟企业且能为投资者提供可预测的现金流量的是()。
下列不属于导游职业道德的是()。
东东看动画片着迷了,饭也不吃。妈妈说:“那你就看个够吧,别吃饭了。”东东就以为真的不用吃饭了。东东不能理解妈妈说的反话,是因为幼儿理解事物具有()。
效力待定民事行为包括()。
Yon’IIfindthatthecommunityhas____greatchangessinceyouwereherelasttime.
最新回复
(
0
)