首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意:算法中涉及的图的基本操作必须在存储结构上实现。)
admin
2019-01-16
49
问题
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点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){ //判断13.个顶点以邻接表示的有向图g中,顶点vi各vj是否有路径, //有则返回1,否则返回0。 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://jikaoti.com/ti/ojfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
从20世纪50年代开始,西欧和日本资本主义经济持续发展的共同原因是()。①政府都推行了一些社会改革,促进了经济发展②都注重发展或引进先进的科学技术、提高劳动生产率③都重视发展教育,培养人才④都接受了国外大量订货,刺激了经济发展
《关于建国以来党的若干历史问题的决议》
反映近代资产阶级政治思想萌芽的著名代表人物是()。
中世纪早期,学者们的思想灵感来源于《圣经》和教会;11世纪初期,西欧的一些主教们在教区内组建学校,并邀请知名学者担当主讲教师;12世纪,教会学校已开设了法学、医学和神学等正式课程。上述材料反映了中世纪时基督教会()。
试析孙中山新旧三民主义中民族主义的内涵、区别与联系。
两宋时期,不同地域曾出现濂、洛、关、阐等学术流派。北宋后期到南宋中期,王安石的新学成为影响最大的学派,这主要是由于()
战国初期,上党地区在下列哪一个国家的控制范围之内()。
晚清时期清帝年号的正确排序是
以下()协议完成了从网卡到IP地址的映射。
随机试题
“三个代表”重要思想的主要贡献是什么?
早期胃癌的概念是()。
基托表面细磨时应保持湿润,其目的是
女,18岁。因大面积烧伤住院治疗3天,上腹疼l天,2小时内排柏油样便3次。查体:P96次/分,BP110/70mmHg,实验室检查:WBC11.8×109/L,血红蛋白92g/L。首选的治疗措施是
对于符合贷款条件的客户,如其资金周转存在一定的周期性,在准确把握其还款能力的基础上,也可以选择按月还息、按计划表还本的还款方式,但此种还款方式下的借款人必须在贷款发生后的第()个月开始偿还首笔贷款本金。
对于危险性较大的重点岗位,生产经营单位应当制定重点岗位的()。
某知名艺人刘某2009年两次在上海举行个人演唱会。其中,第一次票房收入很好,离演出还有一个月,门票就全部售光。于是,该艺人所在经纪公司决定一个月后再次在上海举办刘某个人演唱会,规模与第一次相当。然而,第二次票房收入很不理想,门票仅售出40%。以下
2012年8月,国家人口计生委发布《中国流动人口发展报告2012》。下列关于2011年我国流动人口状况表述错误的是()。
下列哪个语句是声明一个含有10个String对象的数组?()
有以下函数:Functionfun(xAsInteger,yAsInteger)AsIntegerDoWhilex>=yx=x-yLoopfun=xEndFuncti
最新回复
(
0
)