首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-08-15
52
问题
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点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
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
设一段正文由字符集{A,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
以下说法中错误的是()。
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
有效容量为128KB的Cache,每块16字节,8路组相联。字节地址为1234567H的单元调入该Cache,其Tag应是()。
设有一个由正整数组成的无序(后向)单链表,编写能够完成下列功能的算法:(1)找出最小值结点,且打印该数值。(2)若该数值为奇数,则将其与直接后继结点的数值交换。(3)若该数值为偶数,则将其直接后继结点删除。
随机试题
①鼠洞使草场植被破坏严重②苍鹰的羽毛被视为高贵的装饰品③田鼠失去天敌大量繁殖④羊群缺少牧草被迫转场⑤草原上已很难见到苍鹰的影子下列对上述5个事件排序最合理的是()。
患者,男性,68岁。突发胸骨后剧烈疼痛,持续3小时,伴大汗,急诊入院。有吸烟、饮酒史。心电图见图3—11。1小时后,患者症状加重,心电图如图3—12所示,诊断为
A.抗结核治疗B.病灶清除术C.肾部分切除术D.肾切除术E.肾造瘘一侧肾结核无功能,对侧肾重度积水并尿毒症,应先作()
电石仓库属于甲类火灾危险陛场所,在日常监管中要采取特别的措施,下列措施中正确的是()。
桥梁三角网的基线一般采用()。
下列选项中属于可以终止劳动合同的是()。
下列错误中,能够通过试算平衡查找的有()。
编制单位预算的计算方法有()。
认为功能的丧失与特定部位无关,与受损面积有关是哪种脑机能学说的观点?()
在使用UML对数据库应用系统进行建模的过程中,状态图和活动图是常见的动态建模机制。有下列状态图和活动图:Ⅰ.Ⅱ.Ⅲ.Ⅳ.以上状态图或活动图语法正确的是()。
最新回复
(
0
)