首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图G=(V,E)是有向图,V={1,2,…,N},N≥l,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
假定图G=(V,E)是有向图,V={1,2,…,N},N≥l,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求
admin
2019-08-15
23
问题
假定图G=(V,E)是有向图,V={1,2,…,N},N≥l,G以邻接矩阵方式存储,G的邻接矩阵为A,即A是一个二维数组。如果i到j有边,则A[i,j]=1,否则A[i,j]=0。请给出一个算法思想,该算法能判断G是否是非循环图(即G中是否存在回路),要求算法的时间复杂性为D(n
2
)。
选项
答案
此题考查的知识点是图的遍历。采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前碰到某顶点u,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环;否则,无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/adCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
下面关于进程的叙述中,正确的是()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
对n(n≥2)个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中,错误的是____。
如下图所示的AOE网,求:完成此工程最少需要多少天(设边上权值为天数)?
以下关于计算机存储器件的叙述,()是不正确的。
偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中,不属于偏移寻址方式的是____。
随机试题
足太阳膀胱经的主治特点是
小儿高热惊厥的多发年龄是:
甲为了获取超额利润,在明知其所经销的电器产品不符合保障人身安全的国家标准的情况下,仍然大量进货销售,销售金额总计达到180万元。一企业因使用这种电器而导致短路,引起火灾,造成3人轻伤,部分厂房被烧毁,直接经济损失10万元。下列关于甲的行为的说法哪些是正确的
建设永久性测量标志,应当遵守的基本规定有()。
大型工程招标投标工作的评标应采用( )。
关于市场归类决定法说法正确的是()。Ⅰ.使用历史数据估计市盈率Ⅱ.需要有效市场的假定Ⅲ.市盈率的估计,需要选取风险结构类似的公司Ⅳ.使用回归分析法
下列行政案件中,属于中级人民法院管辖的是()。
下列关于我国的公司债说法错误的是()。
从古至今都没有长生不老的人,但每个人的寿命都极不相同,从生物学和医学上来看,人类的寿命应该有一个生物学上的最大值,不过目前尚不能确定人类的最高寿命有多高。这一段话主要支持这样一种观点,即人的寿命()。
下列选项中不属于面向对象程序设计特征的是
最新回复
(
0
)