走有向图
我在该图中有一个有向无环图和一个起点顶点v 。
我如何访问所有可以从v到达的顶点，如果我访问v1我已经访问了所有具有和edge到v1的顶点？
例：
/-----V
A->B->C
从A开始， C必须在B之后访问。
我试着做一个BFS并检查每个顶点的父母，如果他们没有访问过后再重新添加它，但那证明太慢了，我相信可能是O(v^2) 。
这可能有助于知道图形有点二元化，每个顶点将至多指向两个顶点。 在另一个方向上，每个顶点指向许多顶点。
您可能正在寻找一种拓扑排序。
首先，做一个拓扑排序，并根据这种排序得到图中顶点的顺序，让它成为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|)