首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
66
问题
假定图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
学硕统考专业
相关试题推荐
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
以下不属于泰州学派的哲学思想的是()。
在欧美资产阶级革命时代,最能体现出资产阶级革命要求的文献是()。
促成中国近代史上第一次思想解放潮流的是()。
西汉的主要赋税形式中,征收对象是儿童的是()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
随机试题
孙某系某县甲镇人,因涉嫌故意伤害罪被取保候审。孙某在取保候审期间的下列行为,违反了被取保候审人应遵守的规定的有()。
关于小儿尿液特点的描述,正确的有
乳房淋巴引流至
支气管哮喘发作时动脉血气分析的结果常表现为
A.20~30℃B.20~25℃C.5~10℃D.10~15℃E.15~20℃基础状态时的温度要求是
李某2008年通过执业医师考试,在县医院行医师注册后,2年多始终没有上班工作。单位向上级卫生行政部门报告,注销注册。其理由是
( )即选择指数成分股中市值最大的部分股票,按照其在殷价指数所占比例购买,将剩余资金平均分配在剩下的成分股中。
有50名学生选班长,得票最多的人当选,中途计票时发现刘燕已得18票,张军已得16票,李明已得9票,刘燕至少再得多少张票就一定能成为班长?
”类”是面向对象程序设计的关建部分,创建新类不正确的方法是()。
将学号为“25”的学生姓名改为”王莉”,以下SQL语句正确的是()。
最新回复
(
0
)