首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
58
问题
假定图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
学硕统考专业
相关试题推荐
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
晋察冀抗日根据地
东欧剧变中倒下去的第一块多米诺骨牌是()。
在文化大革命中,上海“一月革命”对全国造成的直接影响有()①大串联扩展至全国各地②各省市掀起夺权高潮③各地生产受到严重破坏④武斗事件普遍发生
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
军机处的设置加强了皇权,其最重要的作用是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
在网络中计算机接收的信号是()。
磁盘机由6个盘片组成,其中专设1个盘面为伺服面,其他的盘面作为记录数据的盘面。盘存储区域内直径为6.1cm,外直径为12.9cm,道密度为220TPM,位密度为6000bpm,平均寻道时间为10ms,磁盘转速为7200RPM。假定7π=3,试计算:
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
随机试题
皮亚杰认为,处于具体运算阶段儿童的思维特点有()。
学生动作的执行由出声的外部语言到不出声的外部语言,再到内部语言的过程是智力技能形成的哪个阶段()
头部外伤4小时,CT示侧脑室旁白质、胼胝体压部、大脑脚散在斑点样高密度影。提示有可能是
某甲准备租赁某乙的房屋,双方经协商达成一直意见,下列关于房屋租赁的行为合法的是()。
国家股的资金主要来源有()。Ⅰ.现有国有企业改组为股份公司时所拥有的净资产Ⅱ.现阶段有权代表国家投资的政府部门向新组建的股份公司的投资Ⅲ.经授权代表国家投资的投资公司、资产经营公司、经济实体性总公司等机构向新组建股份公
利润慢慢由正变负是行业()的特点。
关于车辆购置税的计税依据,下列说法中错误的是()。
实行联运的托盘有固定的尺寸标准和有限的种类,我国联运托盘的规格尺寸主要有()三个规格。
人民警察核心价值观是当代人民警察精神的凝练,决定和影响着人民警察的价值取向和行为方式。下列做法体现“公正”这一人民警察核心价值观的是()。
Whydoestheauthormentionthediscoveryofairpressure?Accordingtothepassage,whichofthefollowingisnottrue?
最新回复
(
0
)