首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
admin
2019-08-15
25
问题
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)
选项
答案
用邻接矩阵存储时,可用以下方法实现: 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
学硕统考专业
相关试题推荐
下列关于古日耳曼人的社会状况的叙述中,不正确的是()。
1956年召开的中共八大指出,我国国内主要矛盾的实质是()。
经六朝时期的发展,南方形成了三个农业发达地区即()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
以下叙述不正确的是()。
拿内存加上外存容量之和与虚拟存储空间相比,其大小关系是()。
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用的是()。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下,有效地址EA的表达式。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
在javaEE,下面的哪项配置信息最可能出现在配置文件中()
我国所设的学位等级有()
A.内囊B.外囊C.连合纤维D.投射纤维E.联络纤维连结两侧大脑半球的相应皮质区的是
A、末梢性感觉障碍B、病前感染史C、神经根性疼痛D、四肢弛缓性瘫痪E、单侧面部表情肌肉瘫痪右侧特发性面神经麻痹的体征是
口服毒物病人在洗胃时,每次洗胃液体量为
一些火灾和爆炸的点火源为静电放电火花,为防止静电放电火花引起爆炸,可根据生产过程中的具体情况采取相应的防静电措施。下列措施中,属于防止静电措施的有()
数字出版产品制作流程包括()等环节。
根据《中华人民共和国城市居民委员会组织法》,居民委员会的办公用房由()解决。
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某局使用财政资金进行网络升级改造,分为A、B两包。A包为存储设备及其他配套设备采购项目,B包为网络服务设计项目,包括网络服务器及总集成。【事件1】该局将A包拆分为A1包和A2包,A
Thewritingofahistoricalsynthesisinvolvesintegratingthematerialsavailabletothehistorianintoacomprehensiblewhole.
最新回复
(
0
)