给定一个数字 k 和一个图是否有一个 DFS 运行会给出大于 k 的森林

Question

有人问我一个我似乎无法解决的问题。

给定一个有向图G=(V,E)和一个自然数k，k>0。

找到一种算法，如果存在 DFS 运行树的数量 return “是” 在 DFS 森林中是 >= K.

算法应该与图 G 的大小成线性关系。 O(|V| + |E|).

我会解释：

所以对于以下运行其中 s 是起始节点，我们将得到 2 棵树：

但是如果我们盯着节点 u 看，我们只会得到一棵树。所以我需要 return 是的 k = 1 或 2。没有别的。

那我怎么知道树的数量呢？

感谢您的帮助！

Answer 1

问题编辑后：

使用Kosaraju's algorithm在O(V + E)时间内得到强连通分量。这将给出最大 K.

这里的max K与强连通分量的个数相同。

为什么？

现在让我们用反证法来证明。假设对于问题中显示的图形，我们有 4 个强连通分量。假设有可能从某个节点 v 开始得到一个额外的 dfs 树。这将意味着节点 v 在计算强连接组件的数量时未被覆盖，或者在 DFS 期间遗漏了节点。但是，如果我们使用经过充分验证的算法进行 DFS 或找到强连接组件，则这两种情况都是不可能的。因此，我们的假设是错误的。于是，反证法。

编辑前回答问题：

DFS(Vertex v):
    mark v as visited;
    for(Vertex neighbor: Neighbors of v){
        if(!isVisited(neighbor)){
            DFS(neighbor);
        })
    }

count_trees(Graph G): //V vertices and E edges in total
    for(Vertex v: V){
        if(!isVisited(v)){
            DFS(v);
            trees++;
        })
    }
    return trees;

以上步骤不言自明。维护一个顶点是否被访问是微不足道的。

上述方法只是对每个以前没有访问过的节点进行DFS。因此，时间复杂度与 DFS 相同，即 O(|V| + |E|).

Answer 2

想象给定的图实际上是一棵树。然后，如果您在树的根部启动 DFS，您将在一次 DFS 搜索中找到整个图。在另一个极端，如果你在一片叶子中启动一个 DFS，然后在下一片叶子中启动，并且在节点中启动每个新的 DFS，因为你会得到它们bottom-up，那么每个 DFS 只会找到一个节点然后退出（因为 children 已经被之前的 DFS 访问过了）。因此，您可以启动与树中节点数一样多的 DFS 搜索。

如果图形有一些额外的边，但仍然是非循环的，则同样如此。

当图形有循环时，它就变得不同了。在这种情况下，在循环的任何成员中开始的 DFS 将找到该循环中的所有其他成员。所以一个循环永远不会在不同的 DFS 搜索中分裂。这个循环加上与之相交的所有其他循环，是一个 so-called Strongly connected component.

因此，算法必须找到强连接的组件并将它们计为 1 个 DFS，而所有其他不参与任何循环的节点都可以计为一个单独的 DFS（因为您将从那些子树）。

这是一个算法，它使用 DFS（这令人困惑，因为它是一个计算可能的 DFS 的 DFS）来识别周期并相应地更新计数。我对该算法使用了递归，因此当达到所需的 k 时，必须有一些快速回溯：此外，在这种情况下不需要搜索。

所有边只被访问一次，主循环也只访问所有节点一次，所以达到了所需的时间复杂度。

def k_forests(adj, k):
    # pathindex[node] == 0: means node has not been visited
    # pathindex[node] == -1: means node has been visited and all neighbors processed
    # pathindex[node] > 0: means node is at this step in the current DFS path
    pathindex = [0] * len(adj) # none of the nodes has been visited

    def recur(node, depth):
        nonlocal k  # we will decrease this count

        if pathindex[node] > 0: # cycle back
            return pathindex[node]
        if pathindex[node] == -1: # already processed
            return depth
        pathindex[node] = depth # being visited
        cycle = depth + 1 # infinity
        for neighbor in adj[node]:
            cycle = min(cycle, recur(neighbor, depth + 1))
            if k == 0: # success
                return -1 # backtrack completely...
        if cycle >= depth: # no cylce detected or back out of cycle
            k -= 1
            if k == 0:
                return -1 # success
        pathindex[node] = -1 # completely visited and processed
        return cycle

    # main loop over the nodes
    for node in range(len(adj)):
        recur(node, 1)
        if k == 0:
            return "YES"
    return "NO"

这个函数应该用每个节点的邻接表来调用，其中节点由从0开始的序号标识。例如，问题中的图可以表示如下，其中s = 0， t=1、u=2、v=3、w=4、x=5、y=6 和 z=7：

adj = [
    [4, 7],
    [2, 3],
    [3, 1],
    [0, 4],
    [5],
    [7],
    [5],
    [6, 4]
]

print(k_forests(adj, 4)) #  YES
print(k_forests(adj, 5)) #  NO

给定一个数字 k 和一个图是否有一个 DFS 运行会给出大于 k 的森林

given a number k and a graph is there a DFS run that will give forest larger then k

algorithm

depth-first-search

给定一个数字 k 和一个图是否有一个 DFS 运行 会给出大于 k 的森林

given a number k and a graph is there a DFS run that will give forest larger then k

algorithm

depth-first-search

给定一个数字 k 和一个图是否有一个 DFS 运行会给出大于 k 的森林