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

Question

我搜索过网络,找不到任何DFS算法的解释,用于查找图形的所有关节顶点.甚至没有维基页面.

从阅读中,我从这里了解了基本事实.PDF

每个节点都有一个变量,它实际上是在观察后边缘并找到朝向根节点的最近和最上面的节点.在处理完所有边缘之后,它将被找到.

但我不明白如何在执行DFS期间在每个节点上找到这个向下和向上变量.这个变量到底是做什么的？

请解释算法.

谢谢.

Answer 1

查找关节顶点是DFS的应用.

简而言之,

1. 在图表上应用DFS.获取DFS树.
2. 之前访问过的节点是那些节点的"父节点",它们到达并稍后访问.
3. 如果节点的任何子节点没有到其父节点的任何祖先的路径,则意味着删除此节点会使该子节点与图形不相交.
4. 有一个例外:树的根.如果它有一个以上的孩子,那么它是一个发音点,否则不是.

点3实质上意味着该节点是关节点.

现在对于一个孩子来说,通往该节点祖先的这条路径将通过它的后缘或来自它的任何子节点.

所有这些都在本PDF中得到了很好的解释.

Answer 2

我将尝试对该算法的工作方式进行直观的理解,并提供输出Bi-Components和桥的注释伪代码.

实际上很容易为关节点开发蛮力算法.只需取出一个顶点,然后在图形上运行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