首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
56
问题
假定图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/qACi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
洪武八年,朱元璋仿照元朝的办法,印造(),命令民间通行,形成了钱、钞并用的货币制度
1947年英国通过《蒙巴顿方案》,随后印度和巴基斯坦独立,形成印巴分治局面,在克里米尔地区冲突埋下隐患,《蒙巴顿方案》中印巴分治的依据
梭伦改革的原因、内容及意义。
两极格局结束后,世界形势发展的总态势的基本特点()
1977年4月,对“两个凡是”提出批评,开全党思想解放先河的是()。
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
在一个按字节编址的计算机中,若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H,i的机器数为01234567H,地址:08000000H单元的内容是()。
试比较脱机I/O和联机I/O。
试比较脱机I/O和联机I/O。
随机试题
A.低钾血症B.低钙血症C.等渗性缺水D.高渗性缺水胰十二指肠切除术后患者,禁食,持续胃肠减压,静脉输营养液5天,腹胀,无肛门排气,肠鸣音减弱,腹部无压痛,四肢软弱无力,膝反射减弱,心电图显示T波低宽。该患者存在
颅内压增高时眼部体征有()
重大危险源计算机监控预警系统需要主要监控的状态有()。
FIDIC合同条件规定,当业主与承包商发生合同争议时,提出争议方应首先将自己的要求( )。
施工安全控制基本要求中的安全检查的方式包括()。
计算机网络是以硬件资源、软件资源和信息资源共享以及信息传递为目的,在统一的网络协议控制下,将地理位置分散的许多独立的计算机系统连接在一起所形成的网络。()
下列关于影响客户投资风险承受能力的因素,说法正确的有()。
简述教育对文化的影响。
关于我国河流径流量变化的叙述,正确的是()。
A、 B、 C、 D、 B留意行人和倒在地上的自行车。(A)没有看到女子扔垃圾的场面。(B)能看到人行道上有一台倒着的自行车。(C)没有看到砍倒的树木。(D)bag作动词使用,在商店把东西装到袋子里时使用,考
最新回复
(
0
)