首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
admin
2019-08-01
84
问题
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求算法的时间复杂性为O(n
2
)。
选项
答案
此题考查的知识点是图的遍历。采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前碰到某顶点v,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环;否则,无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/tjCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
以下不属于泰州学派的哲学思想的是()。
洋务运动期间,军事企业主要采取的方式是()。
促成中国近代史上第一次思想解放潮流的是()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是____。
随机试题
若有定义:floatx=1.5;inta=1,b=3,c=2;则正确的switch语句是()。
怎样检修转子式机油泵?
患者,女性,41岁。诊断为“溃疡性结肠”收住入院,每天腹泻5~6次,有少量脓血便。对此患者饮食护理应注意
水肿型急性会厌炎易发生()。
13清单计价规范中,工程量偏差超过(),材料、工程设备单价变化超过价()时,应根据相应规定进行调整。
全面推进依法治国必须全面贯彻和坚持的基本原则是()。
()提出了“经验之塔”。
我国近年来实施了一些重大工程,如:“南水北调”,“西气东输”,“西电东送”等。实施以上工程也说明了:①我国各地区资源分布不平衡②我国在发展市场经济的过程中,国家的宏观调控必不可少③西部的资源优势能变为经济优势④从我国西部运到东部的“气”和“电”都比
以下关于用户界面设计时的颜色搭配的注意事项中,不正确的是_____________。
Surtseywasbornin1963.Scientistssawthebirthofthisisland.Itbeganat7:30a.m.on14thNovember.Afishingboatwas
最新回复
(
0
)