用于查找关节点或切割图的顶点的算法的说明

Question

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

从阅读中，我了解了这里的基本事实。 PDF

在每个节点上都有一个变量，它实际上是在查看后端边缘并找到朝向根节点的最近和最上方的节点。在处理完所有边后，将会找到它。

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

请说明算法。

谢谢。

Answer 1

查找关节顶点是DFS的应用程序。

简而言之，

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

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

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

所有这一切在这PDF精美地解释。

Answer 2

如果u后代的low大于u的dfsnum大，那么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]); 
     } 
    } 
} 

Answer 3

我会尽力制定关于如何算法的工作一个直观的了解，并给予评论伪输出双组件以及桥梁。

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

铰接点连接两个（或更多）子图。这意味着从一个子图到另一个子图没有边。所以想象你在这些子图之一内并访问它的节点。在您访问节点时，您会标记该节点，然后使用某个可用边移动到下一个无标记节点。当你这样做时，你怎么知道你还在同一个子图里？这里的见解是，如果你在同一个子图中，你最终将在访问一个未被标记的节点时通过边缘看到一个被标记的节点。这被称为后沿，表明你有一个循环。一旦找到后端边缘，您可以确信，通过该标记节点的所有节点到您正在访问的节点都是同一子图的一部分，并且两者之间没有关联点。如果您没有看到任何后缘，那么到目前为止您访问的所有节点都是关节点。

所以我们需要为当前存在访问过节点返回边缘的目标之间的访问顶点和标记所有点为同一子图内的算法。子图中显然可能有子图，所以我们需要选择我们迄今为止最大的子图。这些子图被称为双组分。我们可以通过为每个双分量分配一个初始化的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