首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定图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
2023-02-06
51
问题
假定图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://kaotiyun.com/show/MIwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于教师和学生关系的两个对立观点是()。
区角游戏结束时,几个小朋友仍在大声讲话,没有收拾玩具。叶老师轻轻地唱起了收拾玩具的儿歌并把一盒雪花片放进了玩具柜。此时这几个小朋友安静地把玩具送了回去。叶老师运用的教育方法是()。
通常来说,作业有课内和课外两种形式。教师在布置课外作业时要尽量做到“分量适中,难度要大”,以保证学生充分的休息时间和增加学生知识的储备。()
一位老师认为,儿童就像一张白纸,如果给他足够的时间和资源,他能将儿童培养成任何你想要其成为的人。这位老师的观点与教育学家()的教育主张相似。
给定资料: 1.阆中的乡村学校大都依山而建,地形狭长而起伏。在经过若干年的撤点并校之后,形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处,但又会让来访者耳目一新,其中有许多教育局要求的“标配",比如用学生们的彩色大头照拼成的“笑脸墙",师生共同
“十三五”时期,我国航天发射次数占全球的比重为:
有5支足球队进行单循环比赛,每场比赛胜者得3分,负者不得分,平局双方各得1分。比赛结束后,若5支球队的总得分为25分,冠军得12分,则亚军得:
下列年份中,在职职工参保人数同比增速大小排序错误的是:
踢猫效应是指对弱于自己或者等级低于自己的对象发泄不满情绪而产生的连锁反应。“踢猫效应”描绘的是一种典型的不良情绪的传染。人的不满情绪和糟糕心情,一般会沿着等级和强弱组成的社会关系链条依次传递,由金字塔尖一直扩散到最底层,无处发泄的最弱小的那一个元素,则成为
设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域:ch和link,其中ch域为字符类型。
随机试题
A.质量领导组织的职能B.质量管理机构的职能C.质量验收组织的职能D.质量养护组织的职能E.质量检验组织的职能审定企业质量管理制度,设置企业质量管理部门的确定各部门质量管理职能的是()。
下列关于混凝土裂缝处理的说法正确的是()。
某食品企业经营状况最近发生如下变化,银行应重点监控的是()。
关于中国传统节日寒食节,下列说法不正确的是()。
单位让你组织一次会议,当会议时间快到的时候领导来了,还有一些与会人员没到,请问遇到这种情况怎么办?
某个班级的男女生共有51人,男生的3/4等于女生的2/3,问女生有多少人?()
Communicationisthesendingofinformationornewsfromonepersontoanother.Ifhumanbeingscouldnotcommunicatewithonea
OnJanuary1,1901,theCommonwealthofAustraliawasbornoutof______earlycolonies.
Inadditiontoexercisingregularly,eatingagoodbreakfastisconsideredbymanyhealthexpertstobea【B1】______.partofa
Whethertheeyesare"thewindowsofthesoul"isdebatable;thattheyareintenselyimportantin(36)______communicationisa
最新回复
(
0
)