首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
admin
2019-08-01
96
问题
假定图G=(V,E)是有向图,V={1,2,…,N},N≥1,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=l,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求算法的时间复杂性为O(n
2
)。
选项
答案
此题考查的知识点是图的遍历。采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前碰到某顶点v,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环;否则,无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/tjCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比,两者在促进社会变革的作用上有何不同?为什么?
以下不属于泰州学派的哲学思想的是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
二月革命后,为俄国无产阶级革命奠定思想基础的文献是()。
提出“天有常道,地有常数”,“制天命而用之”的思想家是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是____。
随机试题
穿管敷设时,管内导线的总面积(包括绝缘层)不应超过管内截面积的_________%。
以下属于卫生服务需求特点的是
A、甲状腺单纯性囊肿B、甲状腺腺瘤囊变C、与颈前肌粘连,滤泡退化,形成“假囊肿”D、充满胶质的无回声区E、位于甲状腺与舌骨间亚急性甲状腺炎表现为
为防止近效期药品售出后可能发生的过期使用,药品零售企业应当对药品的有效期进行
下列关于环境噪声污染防治的说法中,错误的是()。
人力资源预测的局限性包括()
根据艾森克的人格维度理论,不稳定外倾型表现为好冲动、好斗、易激动等,相当于()气质。
Hewrotealotofnovels,noneof______wastranslatedintoforeignlanguages.
党的十六届六中全会上,我们党提出建设社会主义核心价值体系,其基本内容包括()。
研究显示,相比于农村地区,城市地区居民哮喘、湿疹、过敏性鼻炎和结膜炎等疾病患病率不断攀升。有个假设是乡村生活环境中的某些因素,譬如自小接触到特定细菌能让人免受对某些过敏源的危害,或是城市地区的许多污染物诱发了这些过敏症的发展。对这段文字理解正确的一项是:
最新回复
(
0
)