algorithm - 走有向图

Question

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

例子:

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

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

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

Answer 1

您可能正在寻找 topological sort .

首先做一个拓扑排序，根据这个排序得到图中顶点的顺序，设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|)