algorithm - 使用 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

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

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

对于 s->a、s->b、a->c、b->c、c->d 等情况，我们需要条件 1，以便打印 c。对于 s -> x -> y -> s 这样的情况，我们需要条件 2，以便打印 s。我们需要条件三，例如，​​在上述情况下，打印 d、x 和 y。条件 4 表示这些条件充分。

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

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

状态是:

• 寻找看不见的东西
• 寻找未曾见过的两次

下面是我们处理 6 种可能情况的方法:

1. 寻找看不见的，找到看不见的:标记为见过一次；继续寻找从当前节点看不到的
2. 寻找未见过的，找到已见过的:标记为不止一次见过；打印节点；切换到寻找从当前节点看到一次
3. 寻找未见过的，找到不止一次见过的:死胡同，结束递归分支
4. 寻找not seen twice，find unseen:标记为seen more thance;打印节点；继续寻找没见过两次
5. 寻找没见过两次，找到见过一次:标记为不止一次见过；打印节点；继续寻找没见过两次
6. 寻找两次没见过，发现不止一次见过:死胡同，结束递归分支

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