首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
78
问题
假定图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
学硕统考专业
相关试题推荐
资产阶级维新派创办的第一份刊物是1895年8月康有为在北京创办()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:画出有向带权图G。
快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
若x=103,y=-25,则下列表达式采用8位定点补码运算实现时,会发生溢出的是_______。
若x=103,y=-25,则下列表达式采用8位定点补码运算实现时,会发生溢出的是_______。
随机试题
妊娠合并肠梗阻正确的是
幼儿膳食应遵循平衡膳食的原则,三种功能营养素蛋白质、脂肪与碳水化合物的供给量比例最好保持在
关于药品不良反应含义,说法错误的一项是
属于健康的护理诊断的是
一般而言,与融资租赁筹资相比,发行债券的优点是()。
当公共利益、他人或本人的合法权利受到不法侵害时,行为人所采取的必要的防卫措施,称为紧急避险。()
社会主义改造完成之后,中共八大正确地分析了社会主义改造基本完成以后,中国阶级关系和国内主要矛盾的变化,确定把党的工作重点转向社会主义建设。八大提出的经济建设的方针是
Optimistsoutlivepessimists,anewstudyshows.Ofnearly100,000women【C1】______intheWomen’sHealthInitiative,thosewhoga
KateandMaryaxemy______.Maryoftenlikestoplay______withsomeboys.
OdetotheWestWindwaswrittenby
最新回复
(
0
)