首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2018-08-12
20
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){//输出从顶点start开始的回路 for(i=1;i<=n;i++) if(g[v][i]!=0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为1 printf(“%d”,v); if(i==start)printf(“\n”); else Print(i,start); break; }//if }//Print void dfs(int v){ visited[v]=l; for(j=1;j<=n;j++) if(g[v][j]!=0) //存在边(v,j) if(visited[j]!=1){if(!visited[j])dfs(J);}//if else{cycle=1;Print(j,j);} visited[v]=2; } void find_cycle(){ //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量 for(i=1;i<=n;i++)visited[i]=0; for(i=1;i<=n;i++)if(!visited[i])dfs(i); } 提示:此题考查的知识点是图的遍历。有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问,已访问但其邻接点未访问完,已访问且其邻接点已访问完。下面用0、1、2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。
解析
转载请注明原文地址:https://kaotiyun.com/show/nMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于清朝军机处的叙述,不正确的是()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
隋在统一全国的过程中,平定江南是一个重要的部分,帮助完成岭南一带平定的是()
关于希腊早期宗教的叙述不正确的是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
下列哪一事件之后,明与蒙古之间出现了“自宣大至甘肃,不用兵者二十年”的情形?()
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
已知一个线性表(38,25,74,63,52,48),表长为16,假定采用散列函数h(key)=key%7,计算散列地址,并存储在散列表中,若采用线性探测方法解决冲突,在该散列表上,进行等概率成功查找的平均查找长度为()。
随机试题
Theyoungareontheirwaytomakegreat______(contribute)tosociety.
【背景材料】某大型设备安装工程,由于技术复杂和施工难度大,施工单位对实施设备工程的各项活动作出周密的计算,为使设备合同在合同规定的期限内完成,分别编制了设备工程总进度计划和单体设备进度计划。【问题】
与热力管网闭式系统相比较,开式系统其热媒是被()消耗的。
下列关于国际收支平衡表的描述,正确的是( )。
甲、乙、丙三位出资人共同投资设立丁有限责任公司(以下简称丁公司)。甲、乙出资人按照出资协议的约定按期缴纳了出资额,丙出资人通过与银行串通编造虛假的银行进账单,虚构了出资。ABC会计师事务所的分支机构接受委托对拟设立的丁公司的注册资本进行审验,并委派A注册会
在审核会议文件的具体内容时,首先要审核会议文件内容()。
学生学习三角形后,再学习直角三角形,这种学习称为()。
马铃薯:土豆
Whilemostexperts______theideathatcorporationscouldactuallybecomehumanbeings,mostagreethatpunishingcorporationsfo
论述马卡连柯的集体主义教育思想。
最新回复
(
0
)