首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
63
问题
假定图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
学硕统考专业
相关试题推荐
胡适与李大钊进行“问题与主义之争”的主战场是()。
评述抗战的三个阶段。
试述欧美盟国对德、日法西斯处置的异同,并分析这种现象的原因及影响。
1907年召开的第二国际斯图加特代表大会上,争论最激烈的问题是()。
为了防止谷贱伤农的现象,()向汉文帝提出了人粟拜爵的建议,准许富人买粟输边,按所输多少授予爵位。这一办法的实行,使农民的处境有所改善。
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
在明朝中叶,农业生产发生了一件非常重要的事件——(),对于当时的食物结构产生了重大的影响
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
随机试题
女性,56岁,5年前患乳腺癌手术治疗,术后化疗半年余。半年前发现在左锁骨上淋巴结肿大,2个月来出现胸憋、气短而就诊,化验检查:Hb109g/L,WBC6×109/L,血沉40mm/第1小时末,X线胸片示右肺肿块阴影,心影向两侧扩大,心脏搏动减弱进一步确
金属烤瓷全冠修复时,肩台宽度一般为
肺痨症见干咳少痰,痰中带血,胸部闷痛,手足心热,口咽干燥,时有盗汗,舌红苔薄,脉细数。此证最佳治法是()
张女士,28岁,妊娠6周,出现恶心、呕吐的症状,医生诊断是怀孕初期的正常现象。下列护理措施不妥的是()。
投资估算是建设工程()的投资控制目标。
在施工质量管理的工具和方法巾,直方图一般用来()。
混淆行为是指经营者在市场经营活动中,以种种不实手法对自己的商品或服务作虚假表示、说明或承诺,或不当利用他人的智力劳动成果推销自己的商品或服务,使用户或者消费者产生误解,扰乱市场秩序、损害同业竞争者的利益或者消费者利益的行为。
PromptnessisimportantinAmericanbusiness,academic,andsocialsettings.The【C1】______ofpunctualityistaughttoyoungch
软件文档是软件工程实施中的重要成分,它不仅是软件开发的各阶段的重要依据,而且也影响软件的______。
Whatarethespeakersdiscussing?
最新回复
(
0
)