首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-08-15
47
问题
试写一算法,判断以邻接表方式存储的有向图中是:否存在由顶点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
学硕统考专业
相关试题推荐
下列哪部戏剧不是曹禺的作品()。
“葡萄牙人在非洲海岸、印度和整个远东寻找的是黄金,黄金一词是驱使西班牙人横渡大西洋到美洲去的咒语;黄金是白人刚踏上一个新发现的海岸时所要的第一件东西。”欧洲人对黄金的贪婪追求从本质上反映了()
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
实现一个经典的“读者一写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
对n(n≥2)个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中,错误的是____。
给定二叉树如图A-1所示。设N代表二叉树的根,L代表根结点的左了树,R代表根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2,4,则其遍历方式是____。
已知操作符包括‘+’、‘-’、…、‘/’‘(’和‘)’。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符,若栈初始时为空,则转换过程中同时保存在栈中的操作符的
随机试题
A、Theyareimitations.B、Theyareoriginals.C、TheywerestolenbyanItalianboy.D、Theycamefromthesameartist.B事实细节题。新闻中提
骨盆骨折常见并发症有()
对于依法必须招标的工程建设项目,排名第一的中标候选人(),招标人可以确定排名第二的中标候选人为中标人。
在实践中,各国立法都规定代位求偿权的行使对象不得包括()
期货公司会员应当以()为依据来制定本公司实施方案、建立相关工作制度。
在我国,行政立法的主体是()。
MedicineAwardKicksoffNobelPrizeAnnouncementsTwoscientistswhohavewonpraiseforresearchintothegrowthofcancer
Intherealworldmostpeoplehaveadefinitedislike【C1】______certainsortsofworkathome.Twoofthesetasksareironingclo
Othercommitmentsremainsparsedespitetheplan______since2007.
A、Theweatherismildcomparedtothepastyears.B、Theyarehavingthecoldestwinterever.C、Theweatherwillsoongetwarmer.
最新回复
(
0
)