首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
55
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
国际组织的“民主集中制”原则,是在()文献中首次规定的。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
阅读下列材料,并回答问题:当时帝国地跨欧亚非三洲。地中海成为它的内湖。境内农业、手工业和商业发展起来,海路畅通无阻,陆路纵横交错、四通八达,促进了贸易发展,也有利于信息传递和军队调防。帝国同北欧、印度、中国都有贸易往来,中国的丝绸也传到帝国。原来较落后的
第一个五年计划的具体时间段是()。
中华人民共和国恢复在联合国合法席位的时间是()。
简述“事实判断、成因判断和价值判断”三者的相互关系。
随机试题
Analyzeandcommentonthemeaningsofthefollowingsentencesandthenfindouttherightantonymsforeachfastrespectively.
调节ADH释放最敏感的感受器是
属手∞-3多不饱和脂肪酸的成分是
A.单臂卡环B.双臂卡环C.间隙卡环D.Ⅰ杆卡环E.T形卡环与基牙接触面积最小的卡环为
阴虚动风证的临床特点是()
新型人力资源管理组织机构的表现形式是()。
会计政策是指企业在会计确认、计量、记录和报告中所采用的原则、基础和会计处理方法。()
某旅游开发有限公司2010年8月发生有关业务及收入如下:(1)旅游景点门票收入650万元;(2)景区索道客运收入380万元;(3)民俗文化村项目表演收入120万元;(4)与甲企业签订合作经营协议:以景区内价值2000万元的房
JusthowmuchdoestheConstitutionprotectyourdigitaldata?TheSupremeCourtwillnowconsiderwhetherpolicecansearchthe
不要抛弃学问你们现在要离开母校了。我没有什么礼物送你们,只好送你们一句话罢。这一句话是:“不要抛弃学问。”以前的功课也许有一大部分是为了这张毕业文凭,不得已而做的,从今以后,你们可以依自己的心愿去自由研究了。趁现在年富力强的时候,努力做
最新回复
(
0
)