首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
32
问题
假定图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
学硕统考专业
相关试题推荐
20世纪50年代到70年代初,西欧国家通过有效的社会经济政策,维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革,稳定社会
现代人种出现于人类发展过程中的哪一个时期?()
唐顺宗时,以王叔文、王侄为首的朝臣与宦官之间发生的冲突,称为()。
北宋在统一全国的过程中采用了()战略。
东欧剧变中倒下去的第一块多米诺骨牌是()。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
格拉古兄弟改革
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
随机试题
某农户非法种植大麻近1亩,被村民举报,公安机关在强制铲除时该农户抗拒铲除,对该农户应以非法种植毒品原植物罪和妨害公务罪数罪并罚。
A、150~200mlB、200~250mlC、250~300mlD、2~5LE、4~6L洗胃时每次注入液量约()
鸡圆羽虱在鸡和鸡之间的主要传播途径是
在机场的噪声评价过程中,应当根据飞行量计算到计权等效连续感觉噪声级为()。
下列不属于能源消费总量的有()。
信用证申请书上常见的付款方式有()。
关于公司解散,下列表述正确的是( )。
贷放分控中的“贷”,特指贷款审批通过后,由银行通过审核,将符合放款条件的贷款发放或支付出去的业务环节。()
在确定型决策方法中,常用的方法有()。
2012年3月,宋某与金某共同成立了一家合伙企业。但该企业成立后不久即陷入经营困境,至2012年6月1日,已欠银行贷款12万元。2012年6月2日,宋某的朋友刘某入伙。下列有关刘某权利及义务的表述,不正确的是()。
最新回复
(
0
)