首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
admin
2017-01-04
67
问题
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求算法的时间复杂性为O(n
2
)。
选项
答案
此题考查的知识点是图的遍历。采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前碰到某顶点u,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环;否则,无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/DQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国古代史分期问题的焦点有哪些?简述其代表人物及思想。(兰州大学2013年中国史基础真题)
格拉古兄弟改革的内容和结果是什么?
晚清时期清帝年号的正确排序是()
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
解放军渡江战役中横渡长江的东西两个攻击点是()。
下列哪一项不是凯末尔世俗化改革的内容?()
材料1942年5月,毛泽东指出,对于革命的文艺家,暴露的对象,只能是侵略者、剥削者、压迫者及其在人民中所遗留的恶劣影响,而不能是人民大众。人民大众也是有缺点的,这些缺点应当用人民内部的批评和自我批评来克服。1955年5月,毛泽东在《驳“舆论一律”
为了在通用操作系统管理下的计算机上运行一个程序,需要经历几个步骤,但是,()不是一定需要。
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
随机试题
上颌窦癌向后侵犯可导致
苓桂术甘汤与五苓散组成中均含有的药物是
判断有机磷农药中毒程度最可靠的指标是
下列()不属于房地产产品目标客户需求定位法的步骤。
中国期货业协会、期货交易所依法对期货公司实行()。
在项目建议书批准阶段或之前,各银行可以对符合贷款条件的项目出具贷款意向书,一般没有权限限制。()
设计制作幻灯片母版的菜单是()。
按照利率的决定方式可将利率划分为()。
InternationalHeraldTribune
“雄关漫道真如铁,而今迈步从头越。”经过70多年的持续努力,中国特色社会主义站在新的起跑线上。当今世界正经历百年未有之大变局,不同社会制度、发展模式的竞争较量更为尖锐复杂;中华民族伟大复兴到了关键阶段,建设社会主义现代化强国的任务更为艰巨繁重。未来30年,
最新回复
(
0
)