33

我在网上搜索过，找不到任何关于查找图的所有关节顶点的 DFS 算法的解释。甚至没有维基页面。

通过阅读，我从这里了解了基本事实。PDF格式

每个节点都有一个变量，它实际上是在查看后边缘并找到最接近根节点的最上面的节点。处理完所有边后，就会找到它。

但我不明白在执行 DFS 期间如何在每个节点上找到这个 down & up 变量。这个变量到底在做什么？

请解释算法。

谢谢。

4

4 回答 4

44

寻找关节顶点是 DFS 的一种应用。

简而言之，

  1. 在图上应用 DFS。获取 DFS 树。
  2. 较早访问的节点是它到达并稍后访问的那些节点的“父节点”。
  3. 如果节点的任何子节点没有到其父节点的任何祖先的路径，则意味着删除该节点将使该子节点与图脱节。
  4. 有一个例外：树的根。如果它有多个孩子，那么它是一个关节点，否则不是。

点 3 本质上意味着这个节点是一个关节点。

现在对于一个孩子来说，这条通往节点祖先的路径将通过它或它的任何孩子的后边。

所有这一切都在这个PDF中得到了很好的解释。

于 2013-04-24T23:32:35.313 回答
15

我将尝试对这个算法的工作原理有一个直观的理解，并给出输出双分量和桥的注释伪代码。

为关节点开发蛮力算法实际上很容易。只需取出一个顶点，然后在图上运行 BFS 或 DFS。如果它保持连接，则顶点不是关节点，否则它是。这将O(V(E+V)) = O(EV)及时运行。挑战在于如何在线性时间（即O(E+V)）内做到这一点。

连接点连接两个（或更多）子图。这意味着从一个子图到另一个子图没有边。所以想象你在这些子图之一中并访问它的节点。当你访问节点时，你标记它，然后使用一些可用的边缘移动到下一个未标记的节点。当你这样做的时候，你怎么知道你在同一个子图中？这里的见解是，如果您在同一个子图中，您最终会在访问未标记节点时通过边看到标记节点。这称为后沿，表示您有一个周期。一旦找到后边缘，您就可以确信通过该标记节点到您现在正在访问的节点的所有节点都是同一个子图的一部分，并且两者之间没有关节点。如果你没有

所以我们需要一种算法来访问顶点并将后边目标之间的所有点标记为当前正在访问的节点，就像在同一个子图中一样。显然子图中可能存在子图，因此我们需要选择迄今为止最大的子图。这些子图称为双分量。我们可以通过为每个双组件分配一个 ID 来实现这个算法，该 ID 被初始化为我们迄今为止访问过的顶点数的计数。稍后，当我们找到后边缘时，我们可以将双组件 ID 重置为我们目前找到的最低值。

我们显然需要两次传球。在第一遍中，我们想弄清楚我们可以从每个顶点通过后边看到哪个顶点，如果有的话。在第二遍中，我们希望以相反的方向访问顶点并收集最小的双分量 ID（即，可从任何后代访问的最早祖先）。DFS 自然适合这里。在 DFS 中，我们先下降，然后再上升，因此上述两个通道都可以在一次 DFS 遍历中完成。

现在不用多说，这是伪代码：

time = 0
visited[i] = false for all i
GetArticulationPoints(u)
    visited[u] = true
    u.st = time++
    u.low = v.st    //keeps track of highest ancestor reachable from any descendants
    dfsChild = 0    //needed because if no child then removing this node doesn't decompose graph
    for each ni in adj[i]
        if not visited[ni]
            GetArticulationPoints(ni)
            ++dfsChild
            parents[ni] = u
            u.low = Min(u.low, ni.low)  //while coming back up, get the lowest reachable ancestor from descendants
        else if ni <> parent[u] //while going down, note down the back edges
            u.low = Min(u.low, ni.st)

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node.
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
        Output u as articulation point
        Output edges of u with v.low >= u.low as bridges
    output u.low as bicomponent ID
于 2014-12-30T02:01:26.940 回答
3

似乎所有解释都忽略了一个事实：

事实 #1：在深度优先搜索生成树 (DFSST) 中，每个后边都将一个顶点连接到它的一个祖先。

这对于算法的工作至关重要，这就是为什么任意生成树对算法不起作用的原因。这也是为什么根是一个关节点当且仅当它有超过 1 个子节点的原因：在以生成树的根的子节点为根的子树之间不能有后边。

该语句的证明是，让 (u, v) 成为后边，其中 u 不是 v 的祖先，并且 (WLOG) u 在 DFS 中在 v 之前被访问。假设 p 是 u 和 v 的最深祖先。那么 DFS 将不得不访问 p，然后是 u，然后以某种方式在访问 v 之前再次访问 p。但是在访问 v 之前不可能重新访问 p，因为有一条边u 和 v 之间。

调用 V(c) DFSST 中以 c 为根的子树中的
顶点集

事实2：

对于非根节点 u，
如果 u 有一个子 c 使得 N(c) ⊆ V(c) ∪ {u} 那么 u 是一个关节点。

原因：对于 V(c) 中的每个顶点 w，从根到 w 的每条路径都必须包含 u。如果不是，那么由于事实#1，这样的路径必须包含一个后边缘，它将 u 的祖先连接到 u 的后代，从而使 N(c) 大于 V(c)。

事实 #3：

事实 #2 的反面也是正确的。

原因： u 的每个后代都有一条不经过 u 到根的路径。V(c) 中的后代可以绕过 u，其路径通过连接 V(c) 到 N(c)/V(c) 的后边。

所以对于算法，你只需要知道关于每个非根顶点 u 的两件事：

  1. 顶点的深度，比如 D(u)
  2. N(u) 的最小深度，也称为低点，假设为 L(u)

因此，如果一个顶点 u 有一个子 c，并且 L(c) 小于 D(u)，那么这意味着以 c 为根的子树有一个后边，该边延伸到 u 的祖先，这使得它不是一个关节点事实#3。相反，事实 #2 也是如此。

于 2020-03-16T19:09:11.177 回答
-1

如果low的后代u大于dfsnum的u，则称u其为关节点。

int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];

void cutvertex(int u){
    low[u]=dfsnum[u]=num++;
    for (int v = 0; v < 256; ++v)
    {
        if(adjMatrix[u][v] && dfsnum[v]==-1)
        {
            cutvertex(v);
            if(low[v]>dfsnum[u])    
                cout<<"Cut Vertex: "<<u<<"\n";
            low[u]=min(low[u], low[v]);
        }
        else{
            low[u]=min(low[u], dfsnum[v]);
        }
    }
}
于 2013-10-06T12:18:00.260 回答