首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
70
问题
假定图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
学硕统考专业
相关试题推荐
促成中国近代史上第一次思想解放潮流的是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
随机试题
她很调皮,但对她的恶作剧我们还是会发笑。
孔子说,一种人“和而不同”,还有一种人“同而不和”。下列角色行为属于“和而不同”的是()。
以下几个选项中关于亲职辅导的描述正确的是()。
遥远的自然韩少功城市是人造品的巨量堆积,是一些钢铁、水泥和塑料的构造。标准的城市生活是一种昼夜被电灯操纵、季节被空调机控制、山水正在进入画框和阳台盆景的生活,是一种越来越远离自然的生活。这大概是城市人越来越怀念自然的原因。城市
腹部压痛最显著的部位往往是病变所在之处。
100件产品中有10件次品,每次任取一件,取后放回,则三次抽取恰好取到一件次品的概率为()。
马克思主义政治经济学认为剩余价值()。
中国古代建筑的色彩中等级最高的是()。
在进行薪酬调查分析时,经常使用(),即将调查的同一类数据由高至低排列,再计算出数据排列中的中间数据。
下列说法反映了意识能动性的有()。
最新回复
(
0
)