首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-08-15
28
问题
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点V
i
到顶点V
j
的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
选项
答案
算法1: int visited[]=0; //全局变量,访问数组初始化 int dis(AdjList g,vi){ //以邻接表存储的有向图g,判断vi到vj是否有通路,返回1或0 visited[vi]=l; //visited是访问数组,设顶点的信息就是顶点编号 P=g[vi].firstare; //第一个邻接点 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=l;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中,项点v
i
各v
j
是否有路径, //有则返回1,否则返回O。 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/vdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
南宋理学家()认为一切封建秩序和伦理纲常都是人“本心”所固有的。而不是来自朱熹等人所说的“天理”。他的这一学说被称为“心学”。
鸦片战争失败后,西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点,对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:西方列强在近代中国攫取的第一块殖民地和第一个租界是()
下列选项中,不属于西汉农业发展状况的是()
知识分子思想改造运动
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
网络拓扑结构如下图所示,与C相连接的节点B,E,D的权值分别是6,5,3。如果C收到的三张矢量表分别为:试根据距离矢量路由算法给出C所构造的路由表,并给出计算过程,路由表结构如下表所示。
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
IEEE754标准浮点数的尾数采用()机器数形式。
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
随机试题
锅炉在运行中受高温、压力和腐蚀等的影响,容易造成事故,且事故种类呈现出多种多样的形式。锅炉一旦发生故障,将造成停电、停产、设备损坏,其损失非常严重。下列关于锅炉重大事故应急措施的说法中,正确的是()。
A.美法仑B.巯嘌呤C.塞替派D.卡莫司汀E.异环磷酰胺具有氮杂环丙烷结构的是
肺痈的诊断,主要应掌握下列哪项( )。
男性,40岁,体重60kg,烧伤总面积为60%,伤后第一个24小时补液量是
毒蛇咬伤后,对创口扩创排毒,下列各项中错误的是( )。
建设工程施工任务委托的模式,反映了建设工程项目发包方和承包方之间、承包方与分包方等相互之间的()。
施工测量程序通常遵循()的原则。
大体上来说,教育投资规划工具可分为长期教育投资规划工具和短期教育投资规划工具。短期教育规划工具又包括传统教育投资规划工具和其他工具。()
()是通过色调、影调和光效构成的设计传达给观众直观上的视觉感受。
如下图所示,某校园网使用40Gbps的POS技术与CERNET相连,校园网内部使用OSPF路由协议,与CERNET连接使用静态路由协议。阅读以下R3的部分配置信息,并补充空白处的配置命令或参数,按题目要求完成路由器的相关配置。R3的POS接口配置R
最新回复
(
0
)