有向图 G = (V,E) 中的母顶点是顶点 v,使得所有其他顶点
顶点 G 可以通过从 v 出发的有向路径到达
给出一个 O(n+m) 算法来测试图 G 是否包含母顶点。
(c) 摘自斯基纳手册
只找到 O(n(n+m)) 方式
算法::
a) Do DFS/BFS并跟踪最后完成的顶点 'x' 。
b) 如果存在任何母顶点,则“x”就是其中之一。检查“x”是否是母顶点DFS/BFS从顶点“x”开始。
时间复杂度 O(n+m) + O(n+m) =O(n+m)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)