首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
73
问题
假定图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
学硕统考专业
相关试题推荐
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
若对n阶对称矩阵A[1..n,1..n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定aij(i
快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
随机试题
下列关于中国古琴的说法中,正确的是()。
A.TATA盒B.GC盒C.CAAT盒D.CCAAT盒(2010年第132题)转录因子Spl的结合位点是
A.60°B.30°C.25°D.15°E.45°上颌窦癌两夹角50°照射时,楔形角应取
A.靠近抗原孔B.靠近抗体孔C.在两孔之间D.呈多条沉淀线E.不出现沉淀线双扩试验平板法中,若抗原含量较大,则反应沉淀线应
在估价中测算开发利润应掌握()。
教师讲课过程中的间隔和停顿是运用感知的()。
美国是一个移民国家,学校的学生来自不同的种族与家庭,通过接受系统的学校教育,学生掌握现代文化知识,建立独特的族群和阶层文化,社会也因此充满生机与活力。这主要体现了教育的()
刑法规定,故意杀人情节较轻的,处3年以上10年以下有期徒刑。对此追诉期限为()。
JohnaswellasJack______justbeenbackfromanimportantmeeting.
CareerBuilder.comnowoffersthemostfunctionalandeasy-to-useonlinejobsearchforScience&Biotechjobs.Infact,therea
最新回复
(
0
)