割点与桥 - 元素码农

发布时间: 2025-04-12 11:02

↑

# 割点与桥

## 概述

在图论中，割点（Cut Vertex或Articulation Point）和桥（Bridge或Cut Edge）是衡量图连通性的重要概念。

- **割点**：如果从无向连通图中删除某个顶点及其相关的边后，图变得不再连通，则该顶点称为割点。
- **桥**：如果从无向连通图中删除某条边后，图变得不再连通，则该边称为桥。

这些概念在网络设计、社交网络分析和系统可靠性研究中有重要应用。

## 割点的性质

1. 割点的删除会增加图的连通分量数量。
2. 在一个无环连通图（树）中，除了叶节点外的所有节点都是割点。
3. 在双连通图中不存在割点。

## 桥的性质

1. 桥的删除会增加图的连通分量数量。
2. 在一个无环连通图（树）中，所有边都是桥。
3. 桥不会出现在任何环中。
4. 在边双连通图中不存在桥。

## 寻找割点和桥的算法

### Tarjan算法

Tarjan算法是一种基于深度优先搜索（DFS）的算法，可以在O(V+E)的时间复杂度内找出图中的所有割点和桥。

#### 算法步骤（寻找割点）

1. 对图进行DFS遍历，为每个顶点分配一个DFS序号`dfn[u]`和一个低链值`low[u]`。
2. `dfn[u]`表示顶点u在DFS遍历中的访问顺序。
3. `low[u]`表示从顶点u出发，通过一棵DFS子树可以访问到的最早的顶点的DFS序号。
4. 在DFS过程中，对于当前访问的顶点u和其子节点v：
   - 如果v不通过回边可以访问到u的祖先，且u不是根节点，则u是割点。
   - 如果u是DFS树的根，且u有两个或以上的子节点，则u是割点。

#### 算法步骤（寻找桥）

1. 同样使用DFS遍历，计算每个顶点的`dfn[u]`和`low[u]`。
2. 对于边(u,v)，如果`low[v] > dfn[u]`，则边(u,v)是桥。

### 代码实现

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Graph {
    int V;    // 顶点数
    vector<vector<int>> adj;    // 邻接表
    vector<int> dfn, low;    // DFS序号和低链值
    vector<bool> visited;    // 访问标记
    int time;    // 时间戳
    vector<int> cutVertices;    // 割点
    vector<pair<int, int>> bridges;    // 桥

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
        dfn.resize(V, -1);
        low.resize(V, -1);
        visited.resize(V, false);
        time = 0;
    }

void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

void findCutVerticesAndBridges() {
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, -1);
            }
        }
    }

void dfs(int u, int parent) {
        visited[u] = true;
        dfn[u] = low[u] = ++time;
        int children = 0;

for (int v : adj[u]) {
            if (v == parent) continue;  // 跳过父节点

if (!visited[v]) {
                children++;
                dfs(v, u);

low[u] = min(low[u], low[v]);

// 检查是否为割点
                if (parent != -1 && low[v] >= dfn[u]) {
                    cutVertices.push_back(u);
                }

// 检查是否为桥
                if (low[v] > dfn[u]) {
                    bridges.push_back({u, v});
                }
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }

// 如果是根节点且有多个子节点，则为割点
        if (parent == -1 && children > 1) {
            cutVertices.push_back(u);
        }
    }

void printCutVertices() {
        sort(cutVertices.begin(), cutVertices.end());
        cutVertices.erase(unique(cutVertices.begin(), cutVertices.end()), cutVertices.end());
        
        cout << "割点: ";
        for (int v : cutVertices) {
            cout << v << " ";
        }
        cout << endl;
    }

void printBridges() {
        cout << "桥: ";
        for (auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ") ";
        }
        cout << endl;
    }
};

int main() {
    // 创建一个示例图
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(1, 6);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

g.findCutVerticesAndBridges();
    g.printCutVertices();
    g.printBridges();

return 0;
}
```

## 应用场景

1. **网络可靠性分析**：识别网络中的关键节点和链接，防止网络分割。
2. **社交网络分析**：找出社交网络中的关键人物，这些人物连接不同的社交圈。
3. **交通网络规划**：识别交通网络中的关键路段和交叉点。
4. **分布式系统设计**：确保系统的容错性和可靠性。

## 相关算法

- **双连通分量算法**：用于将图分解为双连通分量，每个双连通分量内部不存在割点。
- **边双连通分量算法**：用于将图分解为边双连通分量，每个边双连通分量内部不存在桥。

## 总结

割点和桥是图论中衡量连通性的重要概念，它们的识别对于分析和优化网络结构具有重要意义。Tarjan算法提供了一种高效的方法来识别这些关键元素，为网络设计和分析提供了有力工具。