3

我有一个 DAG，我需要能够在一个区域内找到一定长度的所有可能路径。例如，我想找到包含至少 3 个但不超过 7 个顶点的所有路径。我的第一个想法是找到一个找到所有路径的算法，然后将它们清除掉。

任何人都可以提供建议吗？

4

1 回答 1

3

枚举所有长度为 K 的路径通常是 O(2^K)，所以我认为上面不枚举所有可能路径的建议是好的。例如：

图表

假设这个图中的所有边都是从左到右的（所以这是一个 DAG）。然后从最左边到最右边的节点有 2^3 条路径（即 2^3 条长度为 6 的路径），因为对于 3 个“钻石”中的每一个，您可以选择采用上面或下面的路径（所以我们正在查看三个二元选择的所有排列）。您可以按照模式扩展图形（通过添加菱形），对于 K 个菱形，将有 2^K 个长度为 2K 的路径。

因此，您可能只想枚举您必须访问的路径（特别是如果它们像您的示例中那样很短）。

我认为上述使用广度优先搜索的建议适用于枚举所有路径，但对于较大的情况，空间需求将是 2^K（当查找长度为 K 或更短的所有路径时）；我这样说是因为你必须记住所有长度为 n-1 的路径才能找到所有长度为 n 的路径。深度优先搜索（或者更确切地说是它的修改版本）也可以：

DFS(int maxLen, Node node):
    list<Node> path
    path.add(node)
    DFS_Helper(maxLen, path)

DFS_Helper(int maxLen, list<Node> path):
    print(path)
    if (path.size() >= maxLen)
        return
    set<Node> targets = graph.getNodesPointedToBy(path.last())
    for Node target in targets:
        path.append(target)
        DFS(maxLen, path)
        path.removeLastNode()

空间使用量为 O(|V|)（V 中的任何顶点，顶点集可以出现在最多一个递归调用的“目标”集中，因为该图是非循环的）。请注意，这仍然会有 O(2^k) 运行时（如上所述，这是不可避免的），我猜由于这种提升不会有现成的算法供您执行此操作（这就是我包含一些伪代码的原因以上）。这不包括下限，但应该不会太糟糕而不能包括在内。

编辑：我最初认为 DFS 的空间使用量是 O(K)，其中 K 是最大路径长度。这是不正确的并且低于实际空间使用量，因为我忽略了在对 DFS_Helper 的每个递归调用中包含“目标”集使用的空间。空间使用量仍然明显低于 BFS。

于 2012-07-21T00:06:44.110 回答