使用 DFS 打印至少两条路径可访问的所有节点

Question

我们如何修改以下 DFS 算法，使其打印出从起始节点 s 起至少有两条路径可访问的所有节点？

DFS(G,s):
        foreach v in V do
            color[v] <- white; p[v] <- nil
        DFS-Visit(s)

    DFS-Visit(u)
        color[u] <- grey
        foreach v in Adj[u] do
            if color[v] = white then 
                p[v] = u; DFS-Visit(v)
        color[u] <- black

例如如果图是树，则不会打印任何节点。如果图形是一个循环，将打印所有节点。

Answer 1

虽然这可以通过运行宁 BFS 而不是 DFS 轻松实现，但也可以通过运行宁 DFS 两次 来实现。

在第一次，当访问一个顶点u时，我们想标记Adj[u]中的每个v是gray 或 black。这意味着这个顶点之前已经被访问过，这意味着它至少有两条路径。我们将通过向顶点添加另一个字段来完成此操作，我们将其命名为 special.

DFS(G,s):
        foreach v in V do
            color[v] <- white; parent[v] <- nil; special[v] <- false
        DFS-Visit(s)

    DFS-Visit(u)
        color[u] <- grey
        foreach v in Adj[u] do
            if color[v] = white then 
                parent[v] = u; DFS-Visit(v)
            if color[v] = gray or color[v] = black
                special[v] <- true
        color[u] <- black

现在我们知道 special[v] == true 的每个顶点 v 至少可以通过两条路径访问。但这还不够——如果你想到一个循环，我们只会将我们开始的顶点标记为 special。这就是为什么我们需要另一个 DFS 运行.

所以我们还想标记所有具有从已标记为 special 的顶点的路径的顶点。我们可以通过运行宁另一个DFS:

DFS(G,s):
        foreach v in V do
            color[v] <- white; parent[v] <- nil
        DFS-Visit(s)

    DFS-Visit(u)
        color[u] <- grey
        foreach v in Adj[u] do
            if special[u] = true
                special[v] = true
            if color[v] = white then 
                parent[v] = u; DFS-Visit(v)
        color[u] <- black

最后，您可以打印具有 special[v] == true.

的每个顶点 v

Answer 2

第一步是写下我们能想到的与我们正在寻找的属性相关的所有规则：存在从 s 到节点的多个不同路径。

如果 u != v 都有到 w 的路径，则至少有两条路径可以到达 w。
如果你有一条到你的路径，那么至少有两条路径可以到达你。
如果 u 通向 v，并且有两条路径到达 u，则至少有两条路径到达 v。
对于通过至少两条路径到达的每个节点，至少满足上述三个条件之一。

对于s->a, s->b, a->c, b->c, c->d这样的情况，我们需要条件1，这样就打印出了c。对于 s -> x -> y -> s 这样的情况，我们需要条件 2，以便打印 s。我们需要条件三，例如，在上述情况下，打印 d、x 和 y。条件4说这些条件就够了。

我们可以通过改变我们的"turn around"条件来修改DFS。当我们看到一个我们已经访问过的节点时，我们不需要 "turning around"，而是简单地改变状态；现在我们不是寻找看不见的节点，而是从这个节点对我们之前只见过一次的节点进行 DFS。在此元 DFS 期间，如果我们看到任何我们之前已经见过两次的东西，我们就会返回；如果我们看到一个我们以前没有见过的，我们将它标记为不止一次看到并继续前进。一旦元 DFS 完成，我们就回到原来的 DFS。所以节点有三个条件，我们有两个状态要跟踪。条件是：

看不见
看过一次
看过不止一次

状态是：

寻找看不见的东西
找了两次没见过

以下是我们处理 6 种可能情况的方法：

寻找看不见的，找到看不见的：标记为见过一次；继续寻找从当前节点看不到的
寻找未见过的，找到已见过的：标记为不止一次见过；打印节点；切换到寻找从当前节点
寻找未见过的，发现不止一次见过：死胡同，结束递归分支
找两次没见过，发现没见过：标记为不止一次见过；打印节点；继续寻找两次不见
找两次没见过，找一次见过：标记为不止一次见过；打印节点；继续寻找两次不见
找两次没见过，找不止一次：死胡同，结束递归分支

规则 1 和 2 需要行为 2。规则 3 需要行为 4 和 5。行为 1、3 和 6 耗尽了我们的其他可能性，并确保在这些情况下规则 4 成立。

使用 DFS 打印至少两条路径可访问的所有节点

Print all nodes accessible by at least two paths using DFS

algorithm

graph-theory

depth-first-search