算法寻找铰接点说明或图形的割点(Explanation of Algorithm for findi

我已经搜查了网，但没有找到一个DFS算法的任何解释查找图的所有关节顶点。甚至没有一个维基页面。

从读书的时候，我才知道从这里的基本事实。 PDF

有在这实际上是在寻找后边缘和寻找朝向根节点最近和最上方的节点的每个节点的变量。处理所有边缘后，它会被发现。

但我不知道如何找到DFS执行过程下来及以上的变量在每一个节点。这是什么变量究竟在做什么？

请解释的算法。

谢谢。

Answer 1:

发现关节顶点是DFS的应用。

简而言之，

在图形上应用DFS。获取DFS树。
这是早些时候访问节点是它被它达到并在稍后访问这些节点的“父母”。
如果一个节点的任何孩子没有任何其父的祖先的路径，这意味着删除此节点将使从图中这个孩子不相交。
有一个例外：在树的根。如果有一个以上的孩子，那么它是一个关节点，否则不是。

点3本质上意味着该节点是一个铰接点。

现在的孩子，这个路径节点的祖先是从通过它或任何其子的后沿。

所有这一切都是在这个美丽的解释PDF 。

Answer 2:

我会尝试开发这是如何算法的工作一个直观的了解，并给予评论伪输出双组件以及桥梁。

它实际上易于开发挂接点的蛮力算法。就掏出一个顶点，并在图表上运行BFS或DFS。如果它仍保持连接，则该顶点不是铰接点，否则是。这将在运行O(V(E+V)) = O(EV)的时间。我们面临的挑战是如何在线性时间做到这一点（即O(E+V)

铰接点连接两个（或更多）子图。这意味着没有边缘从一个子到另一个。所以，想象一下你是这些子图中的一个中和来访的节点。您访问的节点，你标记，然后使用一些可用的边缘移动到下一个未标记节点。当你这样做，你怎么知道你还在同一子图内？这里的观点是，如果你是在同一子图内，你最终会看到一个标记节点通过边缘，而来访的未标记节点。这就是所谓的后边缘，并表示你有一个周期。只要你找到一个后缘，你可以相信，通过所有的节点标记节点您正在访问现在是相同的子图的一部分，并在两者之间没有衔接点之一。如果你没有看到任何背部的边缘，那么所有的节点上，您访问到目前为止都是铰接点。

因此，我们需要的是访问顶点和标记后缘为当前存在访问过的节点的目标之间的所有点为同一子图内的算法。有可能显然是子图中的子图，所以我们需要选择我们至今最大的子图。这些子图被称为双组件。我们可以通过指定每个双组分，其被初始化为只是到目前为止，我们还参观了顶点数量的计数的ID实现这个算法。后来，我们找回来的边缘，我们就可以重新设置双向compinent 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

Answer 3:

如果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]);
        }
    }
}