首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2019-08-15
28
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){ //输出从顶点start开始的回路 for(i=1;i<=13;i++) if(g[v][i]!:0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为l printf("%d",v); if(i==start)printf(”\n”); else Print(i,start); break; }//if }//Print void dfs(int v){ visited[v]=1 ; for(j=l;j<=n;j++) if(g[V][j]!=0) //存在边(v,j) if(visited[J]!=1){if(!visited[j])dfs(j);}//if else{cycle=l;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)结束前出现顶点M到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。
解析
转载请注明原文地址:https://kaotiyun.com/show/SdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
隋唐时期造船业发达的城市是()
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
现有一个长度为3000B的IP数据报,其IP头部的长度为20B,该IP数据报如在最大帧长度为1518B的以太网中进行传输,那么为了正确传输,需要将其拆分的数据报个数是()。
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
在因特网中,IP数据报的传输需要经由源主机和中途路由器到达目的主机,下面说法正确的是()。
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个结点,其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k],则k的值至少为()。
现有一种解决无向连通图的最小生成树的方法:将图中所有边按权重从大到小排序为(e1,e2,…,em);i=1;while(所剩边数≥顶点数){从图中删去ei;若图不再连通,则恢复ei;i++;
随机试题
Hesometimesdoes(add)________workonweekendsintheoffice.
人员素质测评的过程包括________、________、________以及________。
A.慢性规律性的上腹痛B.无规律性的上腹痛C.右上腹绞痛D.左上腹剧痛E.全腹剧痛胆道结石,常表现()
以下高(中)等医学院校不同学制毕业生,不能申请护士执业注册的是
会计要素中反映财务状况的要素不包括()。
采用统计模型法来计算违约概率的理论依据是()。
下列因材施教策略中,不分年级、不同年龄学生在同一课堂学习的教学组织形式是()
近年来西方节日在中国越来越盛行。与之相比,青少年对于中国传统节日的认识明显不足。传统节日已沦为一个吃饭、放假、打折促销的噱头。对此,你怎么看?
博士从一种朝廷备顾问之官转化为一种以教授为主要职能的学官的历史时期是
QuestioningTechniques—AskingQuestionsEffectivelyI.Successfulcommunications:askingtherightque
最新回复
(
0
)