首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2017-01-04
27
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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间是否有路径,如有,则输出 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=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,否则返回0。 for(i=l;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间无通路 提示:此题考查的知识点是图的遍历。在有向图中,判断顶点Vi和顶点vj间是否有路径,可采用搜索的方法,从顶点vi出发,不论是深度优先搜索(DFS)还是宽度优先搜索(BFS),在未退出DFS函数或BFS函数前,若访问到vi,则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则flag=1。
解析
转载请注明原文地址:https://kaotiyun.com/show/WQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列改革内容不是在《天朝天亩制度》中提出的一项是()
论述世界反法西斯联盟的建立过程
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
共产国际“七大”决定加强各国共产党的自主性,主要是由于()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
拉美独立后,各国政治上的一种普遍现象是(),实质上它是拉美各国大地主专政的一种特殊形式。
1890-1906,美南部各州纷纷制定法律或修改州宪法,对公民选举资格进行限定,部分州采用祖父条款,规定内战前有投票格的人,其后代不受新投票规则限制,但该条款被联邦最高法院否定,表明当时美国:
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
A、1B、2C、3D、5C
子产实行的确认土地私有合法性的制度是()
(2010年)管道长度L不变,管中流动为层流,允许的水头损失hf不变,若直径d变为原来的2倍时,且不计局部损失,流量将变为原来的()倍。
安全保证计划是施工组织设计的重要组成部分,下列项目属于计划内容的是()。
()的成立标志着国际评估业走向国际化协助发展的道路。
根据《中华人民共和国出境入境管理法》的规定,下列几类外国人中,()属于不批准出境的。
依据《宪法》规定,有权决定直辖市进入紧急状态的机关是()。
哲学上称之为一元论的是指
真理原则要求是()
Forthispart,youareallowed30minutestowriteashortessayonthetopicofIsOfferingSeatsCompulsoryforYoungPassenge
最新回复
(
0
)