首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
87
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于希腊古风时代和古典时代的叙述不正确的是()。
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
雅各宾派维护大革命成果的主要措施有()。①颁布严禁囤积居奇的法令②改组救国委员会③发布全民皆兵的法令④制定全面限价法令
在西北地区,西北野战军采取了蘑菇战术与敌人周旋,这实际上是()。
下列选项中,对东汉度田问题的描述中,不正确的是()
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
()用铜制造了人体模型,并统一了人体的穴位。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
判断英国工业革命基本完成的主要依据是()
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
随机试题
It’sstrangethatyou______likethatatthemeeting.
A.代表心房除极过程B.代表右心房开始除极至心室开始除极的时间C.代表心室除极的全部过程D.代表心室缓慢复极的过程E.代表心室快速复极的过程P波
与儿童性格的好坏关系密切的因素是
男性,68岁。高血压病史10余年。查体:P56次/分,BP160/90mmHg,血肌酐265umol/L。降压治疗宜首选
背景对某工程施工过程当中的某工作实际进度进行检查后,绘制如下进度计划对比分析图,具体各阶段计划进度与实际进度如下图所示。本工程第一次停顿的原因是由于施工时段正值梅雨期,连续降雨导致无法正常施工。承包商针对第一次停顿的工期延误向建设单位提出相应的工期索
以下属于经济和技术环境的有()。
【2014年威海市真题】有一个小孩,在上中学时,父母曾为他选择文学这条路。只上了一个学期,老师就在他的评语中写下了这样的结论:“该生甩功,但做事过分拘礼和死板,这样的人即使有着完善的品德,也决不能在文学上有所成就。”此后,他改为学习油画,可他极
疾病预防控制中心的研究报告认为,烟草使用是首要的可预防死因,每年全世界有500万人死于烟草相关疾病,其中每年死于二手烟的人数也高达60万,四分之一以上为儿童。以下各项如果为真,哪项最不能质疑上述观点?()
在现代市场经济中,诚信是()
Howwelookandhowweappeartoothersprobablyworriesusmorewhenweareinourteensorearlytwentiesthanatanyotherti
最新回复
(
0
)