走有向图

Question

我有一个有向无环图和该图中的原点顶点v。
我怎样才能访问所有可以从 到达的顶点v，这样如果我访问v1我已经访问了所有具有 和 边的顶点v1？

例子：

/-----V
A->B->C

从 开始A，C必须访问之后B。
我尝试只进行 BFS 并检查每个顶点的父级，如果没有访问它们，则重新添加它以供以后使用，但事实证明这太慢了，我相信可以O(v^2)。

了解该图在某种程度上是二元的可能会有所帮助，每个顶点最多将由两个顶点指向。在另一个方向上，每个顶点都指向很多顶点。

Answer 1

您可能正在寻找拓扑排序。

首先，做一个拓扑排序，根据这个排序得到图中顶点的顺序，令其为v1,v2,...,vn。

使用 BFS，您可以只保留从 可以到达的顶点v（过滤掉其他顶点），并按照拓扑排序的顺序迭代它们。

这是O(|V|+|E|)，在你的情况下是O(|V|)（放松each vertex will be pointed to by at most two vertices表明|E| <= 2|V|，因此O(|V|+|E|) <= O|V|+2|V|) = O(3|V|) = O(|V|)