首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-11-14
33
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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间是否有路径,如有,则输出 inllop=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,否则返回O。 for(i=1;i<=n;i++)visited[i]=0 i //访问标记数组初始化 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间无通路
解析
转载请注明原文地址:https://kaotiyun.com/show/yDRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1543年,发表了解剖学专著《人体结构》的是()。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
下列有关西欧封建社会的表述,错误的一项是()。
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
试述CSMA/CD介质访问控制技术的工作原理。
随机试题
近十余年来,从卵泡液中分离到三个多肽因子,根据其对FSH基因表达的不同作用分别命名为抑制素、激活素和卵泡抑素,对三者的结构与功能已进行了很多研究。关于抑制素表述不正确的是:
白屑风患者调护应注意以下几点,除了:
先天性甲状腺功能减低症服用甲状腺制剂治疗时间是
患儿,男,6岁。以急性肾炎收入院。近2天出现水肿、尿少加重。晨起自诉头晕、恶心、视物不清,应考虑发生
A.六味地黄丸B.桑螵蛸散C.天王补心丹D.金锁固精丸E.朱砂安神丸心肾两虚,虚火内扰而梦遗健忘者,治疗应选用
下列有关液压调速的表述中,不正确的是:( )
下列选项中,作品与作者对应正确的是()。
根据合同法及有关司法解释的规定,下列有关合同解除的表述正确的是()。
以下程序段运行的结果是:______。Dima(-1To5)AsBooleanDimflagAsBooleanflag=FalseDimiAsIntegerDimjAsInteger
A.fatigueB.defectsC.perfectD.improveE.riseF.mistakesG.carefullyH.carelesslyI.ignoreJ.assignmentK.gr
最新回复
(
0
)