首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
67
问题
假定图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
学硕统考专业
相关试题推荐
在欧美资产阶级革命时代,最能体现出资产阶级革命要求的文献是()。
促成中国近代史上第一次思想解放潮流的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
随机试题
20世纪50年代末至60年代末,西方世界发生了一场指向于教育内容现代化的课程改革,这场运动是()
A公司是某市一家中等规模的企业,拥有职工800余人。公司在2003年初创立时,主要给其他企业做OEM(贴牌生产),生产一些通用性强的电子零部件,品种不多,设计定型,新产品也很少。当时公司设开发、制造、销售等部门。其中,制造部门是主要部门,开发部门和销售部门
DIC常见病因除外
A.心俞B.肝俞C.脾俞D.肺俞E.肾俞
晕针是在针灸过程中常见的针刺异常情况,下列关于晕针的处理措施,正确的有()。
某场地湿陷性黄土厚度为10~13m,平均干密度为1.24g/cm3,设计拟采用灰土挤密桩法进行处理,要求处理后桩间土最大干密度达到1.60g/cm3。挤密桩正三角形布置,桩长为13m,预钻孔直径为300mm,挤密填料孔直径为600mm。问满足设计要求的灰土
HS是一家具有60多年历史的大型国有制造企业,主营业务为工程机械产品制造.人员规模2000余人,主要面对华北和西北市场。由于中国工程机械市场在2001年爆发性增长,企业销售规模增长迅速,在2002年到2005年之间,销售收入从16亿增长到30亿左右,成为行
试述中华全国总工会的工作职责。
设a=(1,0,一1)T,矩阵A=aaT,n为正整数,a为常数,则∣aE一An∣=_______.
Manypeoplewonderwhysomemenwanttoliveonthemoon.Itis【1】notthekindofplacewheremostmenwouldchoosetolive.But
最新回复
(
0
)