首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
86
问题
假定图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世纪法国启蒙思想相比,两者在促进社会变革的作用上有何不同?为什么?
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
促成中国近代史上第一次思想解放潮流的是()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
高度为7的AVL树最少有()个结点。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是____。
随机试题
我茫茫然走在路上,一个汉子迎面而来,冲着我唤:“苏婉娜,苏——婉——娜……我吃了一惊,停住步,那汉子也一怔,流泛出-脸腼腆与失望,低着头喋喋地说:“对不起,我认错了.....我定一定神,接着是怦然而动的心跳。这汉子脸上的腼腆和忸怩的神态
采用火焰矫直缓弯曲变形的实芯轴杆件时,应采用()加热方式。
《过秦论》“一夫作难而七庙隳”中的“一夫”是指
下列有关G蛋白的描述,错误的是
宏观经济状况包括经济发展水平、状况和前景等方面。经济发展水平对银行的经营管理产生直接影响,经济发展的状况和前景对银行的经营管理产生间接影响。()
下列关于名牌效应的说法错误的是()。
下列有关宪法的说法正确的有()
在日本经济雄视天下的时候,很多企业家涌入艺术品市场,大肆搜罗西方印象派的作品。后来随着经济泡沫的破裂,日本艺术品购买力一落千丈,那些艺术大师的经典作品,恰似万顷波涛上的巨轮,尚能岿然不动;那些平凡之作却是小舢板,在风雨飘摇中不堪一击,其所有者难免遭受灭顶之
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
A、 B、 C、 A注意不要只听了问题中的test就将其与选项(B)中的study联系到一起而错误地选择选项(B)。另外还要注意不要忽略了选项(C)中的he’s,不然就很容易将其误选为正确答案。
最新回复
(
0
)