首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
2017-01-04
33
问题
假定图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://jikaoti.com/ti/i6fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。
《关于建国以来党的若干历史问题的决议》
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
下列关于湘军的叙述中不正确的是()。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
下列几种排序方法中,要求内存量最大的是()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
随机试题
设z=x2f(),且f可微,求dz.
决定硬膜外阻滞平面的最主要因素是_____。
碘解磷定
某仲裁机构对甲公司与乙公司之间的合同纠纷进行裁决后,乙公司不履行仲裁裁决。甲公司向法院申请强制执行,乙公司申请法院裁定不予执行。经审查,法院认为乙公司的申请理由成立,裁定不予执行该仲裁裁决。对此,下列说法错误的是:()
求取土地收益及确定()是收益还原法的关键。
净化空调系统的终端过滤设备和净化设备的核心是()。
会计记录所使用的文字只能是中文,不允许使用民族文字或外国文字。()
著作权中,()的保护期不受限制。
结合我省实际,谈谈如何进行依法治省?
--Wouldyouliketogopicnickingwithustoday?--______,butitlookslikerain.
最新回复
(
0
)