首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-08-15
44
问题
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点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
学硕统考专业
相关试题推荐
1939年前后,中国政治思想界展开关于三民主义问题争论的根本原因是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题在武王灭商和周公东征的过程中立有大功,或与周有世代同盟关系的异姓贵族也被分封去建立诸侯国家,继续为周王室效力,下列国家:①齐②鲁③燕④宋,属于异姓诸侯国的是(
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
在一个双链表中,在*p结点之前插入*q结点的操作是()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
下面关于图的存储的叙述中,正确的是()。
某网络拓扑如下图所示,路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有的子网,则在R1中需要增加的一条路由(目的网络,子网掩码,下一跳)是____。
随机试题
竞争性抑制作用的特点是
目前已发现的内源性阿片样肽类有()
对经营品种比较单一,经营地点、时间和商品来源不固定的纳税人进行的税款征收方式是( )。
A公司2015年财务报告批准报出日为2016年4月30日。A公司2016年1月6日向乙公司销售一批商品并确认收入。2016年2月20日,乙公司因产品质量原因将上述商品退回。A公司对此项退货业务正确的处理方法是()。
引证法的形式有()
财务分析中的效率指标,是某项财务活动中所费与所得之间的比率,反映投入与产出的关系。()
安全通道为建筑物消防安全必须拥有,用于应急逃生和消防救助的快速通道。下列表示安全通道标志的图标的是()。
商品的价值是()
“http://www.rkb.gov.cn”中的“gov”代表的是______。
结构化设计方法所设计的模块具有诸多特点,下列不属于结构化设计方法中所设计的模块的特点的是
最新回复
(
0
)