首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2018-08-12
57
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: 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
学硕统考专业
相关试题推荐
关于垄断组织的积极作用,不正确的说法是()。
下面有关兵制的内容,与唐玄宗有关的是()
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
论述十字军运动(十字军东征)发生的背景、过程及其影响。
关于“一战”后构筑的凡尔赛体系,说法不正确的是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
商朝号称青铜时代,下列叙述不符合当时的历史情况的是()
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
随机试题
根据《民事诉讼法》及相关规定,下列关于诉前财产保全的说法,正确的是?
根据《会计法》和《总会计师条例》的规定,总会计师的任职条件是_________。
阳光的香味林清玄我遇见一位年轻的农夫。在南方一个充满阳光的小镇。那时是春末,一季稻谷刚刚收成,春日阳光的金线如雨倾盆地泼在温暖的土地上,牵牛花在篱笆上缠绵
下列生物碱碱性最强的是()
乙状结肠扭转的典型的影像学表现是小肠扭转的典型的影像学表现是
A.700mg/dB.800mg/dC.15mg/dD.20mg/dE.45mg/dWHO推荐的孕妇锌供给量标准为()
国家对用于()的列入强制检定目录的工作计量器具实行强制检定。
我国《海关法》规定,除法定减免税以外,关税的减免权限属于()。
下列不属于110报警服务台受理报警范围的是()。
根据下列资料,回答下列问题。2010年,浙江省进出口总额为2534.7亿美元,比上年增长35%,其中进口729.9亿美元,增长33.4%;出口1804.8亿美元,增长35.7%,出口占全国的比重从上年的11.1%提高到11.4%。
最新回复
(
0
)