如何按优先顺序获取 DAG 顶点的祖先？

Question

对于有向无环图中的给定节点，我想获取该节点的所有祖先的列表，以便它们满足优先顺序

假设这是一个代表任务及其前序的 DAG。

现在假设我想做工作E，那么我必须先做工作[A，B]。

因此对于输入 DAG 和节点 E 输出应该是 [A, B]。

我想要一个算法。

Answer 1

查找特定目标顶点的祖先：

dfs(v):
    mark v as visited
    for every neighbor u of v:
        if u is unvisited:
            if u is target vertex:
                return true
            if dfs(u) is true:
                put u in result set
                return true
        else
            if u is in result set:
                return true
    return false

for every unvisited vertex v:
    if dfs(v) is true:
        put v in result set

return result set

O(V + E) 时间复杂度。

---

Topological sort：这将为您提供 O(V + E) 时间复杂度中所有顶点所需的顺序。