首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
48
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
巴黎和会讨论的中心问题是()。
在粉碎国民党对陕北的重点进攻时,西北野战军采用的“蘑菇”战术实际上属于()
使用天然火最早出现于人类发展过程的哪一阶段?()
规定了电流、电动势、电阻等概念的物理学家是()。
不属于第三次科技革命新特点的选项是()。
“改土归流”政策的根本目的是()。
说俄国1861年改革是资产阶级性质的改革,美国内战是第二次资产阶级革命,其共同的根本依据是()。
试述西欧城市兴起的原因、方式及其影响。
20世纪五六十年代经济高速增长时期,西欧经济增长最快的国家是()。
随机试题
患者,男,46岁,发热头痛两天。查体:右下唇黏膜充血,并有糜烂面,表面有灰白色的假膜,略高于黏膜表面,光滑致密,病变周界清楚。颏下淋巴结肿大,并有压痛。根据临床表现,该病的诊断是()。
在室温条件下,对有明显屈服现象的钢材标准试样进行拉伸试验,通常取上屈服强度作为屈服强度特征值。()
地籍图精度的检测方法通常用图解距离与相应的解析反算边长、检测距离或宗地草图上注记的原测距离进行比较,其较差的中误差不得大于以上要求,较差的允许误差不得大于()中误差。
预先危险性分析中的危险等级如何划分?
内存中的随机存储器通常是用()来表示的。
根据下面材料回答下列问题。根据上表,下列说法不正确的是()。
《学记》将大学教育的年限划分为两个阶段,第一阶段从第一年到第七年,第二阶段从第八年到第九年,第九年考试合格,称之为()。
设α,β为四维非零列向量,且α⊥β,令A=αβT,则A的线性无关特征向量个数为().
Tourismisoneofthemostpromisingindustriesofthelastfewyears.Inmostcountriesthereareofficialorganizationstoenc
Itis【C1】______spring,andallofusarethankfultoseetreesbloomingandbirds【C2】______tonestagain.Justaboutallof
最新回复
(
0
)