试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。

admin2017-04-28  38

问题 试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。

选项

答案时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。

解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
0

最新回复(0)