首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
57
问题
假定图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
学硕统考专业
相关试题推荐
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
《共产党宣言》的基本思想、内容及历史意义是什么?
简述雅典民主政治的形成过程。
以下不是巴黎和会的主要议题的是()
下列关于湘军的叙述中不正确的是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
某计算机主存按字节编址,逻辑地址和物理地址都是32位,页表项大小为4字节。请回答下列问题。若使用二级页表的分页存储管理方式,逻辑地址结构为:设逻辑地址为LA,请分别给出其对应的页日录号和页表索引的表达式。
随机试题
呕吐“呕而发热者,______主之。”
考虑函数y=x2,0≤x≤1,问t取何值时,图中阴影部分的面积S1与S2之和S1=S1+S2最小;t取何值时,面积S=S1+S2最大.
A.X线B.CTC.MRID.B超E.MRA欲显示鼻窦部各种解剖结构的关系首选的影像学检查方法是
A.法律B.行政法规C.部门规章D.司法解释E.现行宪法《药品说明书和标签管理规定》是由国家食品药品监督管理局发布的
世贸组织的协定给予发展中成员例外的特殊和差别待遇,下列不属于对发展中成员的差别优惠待遇的是______。
某公司与质检员工签订劳动合同约定:如果业务量为0—500件,支付工资2000元;如果业务量为501—800件,支付工资2500元;如果业务量为801—1000件,支付工资3000元,1000件以上(不包括1000件),支付工资3500元。根据成本性态分析,
根据2019年政府工作报告,将上升为国家战略并编制实施发展规划纲要的是
很多地方为了举办大型赛事,投入巨资修建体育场馆,但是承办完一次大型活动后,场馆大多被闲置,造成资源浪费。对此,你怎么看?
某工厂生产甲、乙两种产品,当这两种产品的产量分别为x和y(单位:吨)时的总收益函数为R(x,y)=42x+27y一4x2—2xy—y2,总成本函数为C(x,y)=36+8x+12y(单位:万元).除此之外,生产甲、乙两种产品每吨还需分别支付排污费2万元,1
1/3+3/7=______
最新回复
(
0
)