algorithm - 使用贪心算法访问 DAG 中的所有节点

Question

我正在尝试使用贪心算法访问有向无环图中的所有节点。我在想像深度优先搜索这样的东西会起作用，但我不确定这将如何与 DAG 一起使用，因为我无法通过图表追溯自己。

谢谢。

Answer 1

是的，您可以使用深度优先搜索 (DFS) 或广度优先搜索 (BFS)，查看任何好的教科书，例如 Thomas H. Cormen 的“算法简介”。

您不需要使用边来“追溯自己”，使用堆栈（或递归）或队列。

Answer 2

void dfs(node V) {
    mark V as visited;
    for each edge E, so that E.source = V, do {
        if(E.destination is not marked as visited) {
            dfs(E.destination);
        }
    }
}

而已。DFS(recursion) 的作用是在当前实例完成时返回其调用者实例。由于它使用堆栈来保存所有活动实例，因此您不必自己返回，当函数在当前节点上完成执行时，它会自动回滚到前一个节点。