使用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就被打印出来了。我们需要条件3，例如，在上面的例子中，d、x和y被打印出来。条件4说这些条件是充分的。

我们可以通过改变"turn around"条件来修改DFS。当我们看到一个已经访问过的节点时，我们不会"转身"，而是简单地改变状态;现在，我们不再寻找看不见的节点，而是从这个节点对我们以前见过一次的节点进行DFS。在这个元DFS中，如果我们看到任何我们已经见过两次的东西，我们就会回头;如果我们看到一个以前没见过的，我们就把它标记为不止一次，然后继续前进。一旦元DFS完成，我们就返回到原始DFS。所以节点有三种条件我们有两种状态需要跟踪。条件:

• 看不见的
<
• 看过一次/gh>
• 出现一次以上

状态:

• 寻找看不见的
• 查找未被看到两次

下面是我们如何处理这六种可能的情况:

1. 寻找看不见的，发现看不见的:标记为见过一次;继续查找当前节点中未见的
2. 寻找未见过的，找到见过的:标记为见过多次;打印节点;切换到从当前节点查找见过一次
3. 寻找未见过的，发现见过不止一次:死胡同，结束递归分支
4. 寻找未见过两次的，发现未见过:标记为见过不止一次;打印节点;继续搜索not seen twice
5. 寻找未见过两次的，找到见过一次:标记为见过多次;打印节点;继续搜索not seen twice
6. 查找not seen两次，查找not seen不止一次:dead end，结束递归分支

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

Answer 2

虽然这可以通过运行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

现在我们知道每个顶点v, special[v] == true至少可以被两条路径访问。但这还不够——如果你考虑一个循环，我们将只标记我们开始的顶点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

最后你可以打印每个顶点v有special[v] == true