图的割点与桥（Articulation Points and Bridges）

一、知识点描述
图的割点（Articulation Point，也称关节点）和桥（Bridge，也称割边）是图论中的重要概念，用于分析图的连通性与脆弱性。

• 割点：在一个无向连通图中，如果删除某个顶点及其关联的边后，图不再连通，则该顶点称为割点。
• 桥：在一个无向连通图中，如果删除某条边后，图不再连通，则该边称为桥。

这两个概念在网络可靠性、交通规划、社交网络分析中有重要应用。例如，识别通信网络中的关键节点（割点）或关键连接（桥），可帮助设计容错系统。

二、基础概念与定义

1. 无向连通图：图中任意两个顶点间都存在路径。
2. 深度优先搜索（DFS）树：对图进行DFS遍历生成的树结构，包含树边（Tree Edge）和返祖边（Back Edge）。
3. 发现时间（discovery time）：在DFS中访问顶点的顺序编号，记为 disc[u]。
4. 最低访问时间（low time）：对于顶点 u，low[u] 表示从 u 或其子孙通过一条返祖边能到达的最早访问的顶点编号。计算方式为：
   • low[u] = min(disc[u], disc[v])，其中 v 是 u 通过返祖边直接到达的祖先。
   • low[u] = min(low[u], low[w])，其中 w 是 u 在DFS树中的子节点。

三、寻找割点的算法（Tarjan算法）
步骤：

1. 对图进行DFS遍历，记录每个顶点的 disc[u] 和 low[u]。
2. 判断割点的条件：
   • 根节点：如果DFS树的根节点有至少两个子节点，则根节点是割点。
   • 非根节点：对于顶点 u，如果存在一个子节点 v 满足 low[v] >= disc[u]，则 u 是割点。
     解释：条件 low[v] >= disc[u] 表示从 v 及其子孙无法通过返祖边到达 u 的祖先，删除 u 后 v 的子树与图其余部分断开。

算法伪代码（递归DFS实现）：

时间戳 time = 0
function findCutVertices(u, visited, disc, low, parent, isAP):
    visited[u] = true
    disc[u] = low[u] = ++time
    子节点数 children = 0
    
    for 每个邻接点 v of u:
        if not visited[v]:
            children++
            parent[v] = u
            findCutVertices(v, visited, disc, low, parent, isAP)
            # 回溯后更新 low[u]
            low[u] = min(low[u], low[v])
            
            # 判断割点条件
            if parent[u] == NIL and children > 1:
                isAP[u] = true
            if parent[u] != NIL and low[v] >= disc[u]:
                isAP[u] = true
        else if v != parent[u]:  # 处理返祖边
            low[u] = min(low[u], disc[v])

示例：考虑一个简单无向图：
顶点：0-1-2 形成链状。

• 顶点1的删除会使图变成两个分支（0和2不连通），因此顶点1是割点。
• 根节点0只有1个子节点，不是割点。
  通过计算 disc 和 low 可验证条件。

四、寻找桥的算法
步骤：

1. 类似割点算法，进行DFS并计算 disc 和 low。
2. 判断桥的条件：对于边 (u, v)，如果 low[v] > disc[u]，则 (u, v) 是桥。
   解释：条件表示从 v 及其子孙无法通过返祖边到达 u 或更早的顶点，删除该边后 v 的子树与图其余部分断开。

算法伪代码（在DFS中检测）：

function findBridges(u, visited, disc, low, parent, bridges):
    visited[u] = true
    disc[u] = low[u] = ++time
    
    for 每个邻接点 v of u:
        if not visited[v]:
            parent[v] = u
            findBridges(v, visited, disc, low, parent, bridges)
            low[u] = min(low[u], low[v])
            
            # 判断桥条件
            if low[v] > disc[u]:
                bridges.add((u, v))
        else if v != parent[u]:
            low[u] = min(low[u], disc[v])

示例：图同上（0-1-2）。

• 边 (0,1)：计算得 low[1]=1，disc[0]=0，low[1] > disc[0] 不成立（1=1），不是桥。
• 边 (1,2)：low[2]=2，disc[1]=1，low[2] > disc[1] 成立（2>1），是桥。

五、算法复杂度与注意事项

• 时间复杂度：O(V + E)，基于DFS遍历。
• 空间复杂度：O(V)，用于存储 visited、disc、low 等数组。
• 注意事项：
  1. 图必须是无向连通图，若图不连通需对每个连通分量分别应用算法。
  2. 处理重边时，需注意返祖边的判断：只有非父节点的已访问邻接点才考虑。
  3. 对于根节点，割点条件基于子节点数，而非 low 值比较。

六、应用场景

1. 网络设计：识别关键路由器（割点）或关键链路（桥），增强冗余。
2. 社交网络：找到连接不同社区的“桥梁人物”。
3. 电路板设计：避免因单点失效导致电路断开。

通过掌握割点与桥的判定算法，你可以深入理解图的结构特性，并为解决更复杂的图论问题（如双连通分量、最小割等）打下基础。