首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
2019-08-01
28
问题
假定图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中是否存在回路),要求算法的时间复杂性为D(n
2
)。
选项
答案
此题考查的知识点是图的遍历。采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前碰到某顶点u,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环;否则,无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/X8Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
某新石噐遗址发现大量稻谷壳和稻草,红士,防洪水城垣,此遗址可能是
对1929—1933年的世界经济危机的特点,表述不正确的是()。
为了顺利开展武装起义的准备工作,在彼得格勒苏维埃中成立了()。
【凯南遏制政策】(八千字电文)华东师范大学2000年世界当代史真题;南京师范大学2013年历史学综合真题
编写判定给定的二叉树是否是二叉排序树的函数。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
设有A,B,C,D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.28.112,B主机的IP地址是192.155.28.120,C主机的IP地址是192.155.28.135,D主机的IP地址是192.155.28.202。共同的子网掩
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
随机试题
读我国某区域示意图,完成下列问题。该区域水稻种植北界不断北移、种植面积不断扩大的主要自然原因是()。
A.孕7周内B.孕7~10周C.孕11~14周D.孕15~24周E.孕25~28周口服药物流产适用于
保持血中甲状腺激素的稳定依靠过量碘产生的抗甲状腺聚碘作用是
在反倾销过程中,终裁决定确定的反倾销税,高于已付或者应付的临时反倾销税或者为担保目的而估计的金额的,()。
根据我国立法规定,下列哪些场合可以适用公共秩序保留制度?()
下列不属于UFO报表文件拓展名的是()。
案例:师:同学们,上节课我们学习了牛顿第一定律的有关知识,你们会背牛顿第一定律的内容吗?生:一切物体在没有受到力的作用时,总保持静止状态或匀速直线运动状态。师:很好,看来同学们对于上节课的知识掌握得非常扎实。大家想物体在不受力
某游泳池有A、B、C三个进水管,先开A、B两管,3小时后,关闭A管打开C管,又过了3小时,关闭B、C两管,经测算,还需开A管注水半小时或者开B管注水45分钟才可将游泳池注满。已知A、B两管注水1小时相当于C管注水2小时,问三管齐开,多长时间可以将游泳池注满
(2015广东)有两箱数量相同的文件需要整理。小张单独整理好一箱文件要用4.5小时,小钱要用9小时,小周要用3小时。小周和小张一起整理第一箱文件,小钱同时开始整理第二箱文件。一段时间后,小周又转去和小钱一起整理第二箱文件,最后两箱文件同时整理完毕。则小周和
这次新机种试飞只是一次例行试验,既不能算成功,也不能算不成功。以下哪项对于题干的评价最为恰当?
最新回复
(
0
)