并查集算法 - 元素码农

发布时间: 2025-03-21 19:25

↑

# 并查集算法

并查集（Union-Find）是一种用于处理不相交集合的数据结构，主要支持两种操作：合并（Union）和查找（Find）。本文将详细介绍并查集的原理、实现和应用。

## 基本概念

### 不相交集合

不相交集合是指多个集合之间没有共同的元素。并查集通过树形结构来维护这些集合，每个集合用一棵树表示，树的根节点是该集合的代表元素。

### 基本操作

1. Find(x)：查找元素x所属的集合（返回该集合的代表元素）
2. Union(x,y)：合并元素x和y所属的集合
3. Connected(x,y)：判断元素x和y是否属于同一个集合

## 算法原理

### 数据结构

并查集使用一个数组parent[]来表示每个元素的父节点：
- parent[x] = x 表示x是根节点
- parent[x] = y 表示x的父节点是y

### 基本实现

```go
type UnionFind struct {
    parent []int
}

func NewUnionFind(size int) *UnionFind {
    parent := make([]int, size)
    for i := range parent {
        parent[i] = i  // 初始时每个元素都是一个单独的集合
    }
    return &UnionFind{parent: parent}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])  // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX != rootY {
        uf.parent[rootX] = rootY
    }
}

func (uf *UnionFind) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}
```

### 优化技巧

1. 路径压缩
   - 在Find操作时，将查找路径上的所有节点直接连接到根节点
   - 显著减少树的高度，提高后续操作的效率

2. 按秩合并
   - 记录每个树的高度（秩）
   - 总是将较矮的树合并到较高的树下
   - 控制树的高度增长

```go
type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(size int) *UnionFind {
    parent := make([]int, size)
    rank := make([]int, size)
    for i := range parent {
        parent[i] = i
    }
    return &UnionFind{
        parent: parent,
        rank:   rank,
    }
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])  // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX == rootY {
        return
    }
    
    // 按秩合并
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
}
```

## 应用示例

### 网络连接判断

```go
type Network struct {
    nodes     int
    unionFind *UnionFind
}

func NewNetwork(n int) *Network {
    return &Network{
        nodes:     n,
        unionFind: NewUnionFind(n),
    }
}

func (n *Network) Connect(x, y int) {
    n.unionFind.Union(x, y)
}

func (n *Network) IsConnected(x, y int) bool {
    return n.unionFind.Connected(x, y)
}

// 使用示例
func main() {
    network := NewNetwork(10)
    
    // 连接节点
    network.Connect(1, 2)
    network.Connect(2, 3)
    network.Connect(4, 5)
    
    // 检查连接性
    fmt.Println(network.IsConnected(1, 3))  // true
    fmt.Println(network.IsConnected(1, 4))  // false
}
```

### 动态连通性问题

```go
type DynamicConnectivity struct {
    uf *UnionFind
}

func NewDynamicConnectivity(n int) *DynamicConnectivity {
    return &DynamicConnectivity{
        uf: NewUnionFind(n),
    }
}

func (dc *DynamicConnectivity) Connect(p, q int) {
    dc.uf.Union(p, q)
}

func (dc *DynamicConnectivity) IsConnected(p, q int) bool {
    return dc.uf.Connected(p, q)
}

func (dc *DynamicConnectivity) Count() int {
    count := 0
    for i := 0; i < len(dc.uf.parent); i++ {
        if dc.uf.parent[i] == i {
            count++
        }
    }
    return count
}

// 使用示例
func main() {
    dc := NewDynamicConnectivity(10)
    
    // 添加连接
    connections := []struct{ p, q int }{
        {4, 3},
        {3, 8},
        {6, 5},
        {9, 4},
        {2, 1},
    }
    
    for _, conn := range connections {
        if !dc.IsConnected(conn.p, conn.q) {
            dc.Connect(conn.p, conn.q)
            fmt.Printf("连接 %d-%d\n", conn.p, conn.q)
        }
    }
    
    fmt.Printf("连通分量数量: %d\n", dc.Count())
}
```

### 图的环检测

```go
type Graph struct {
    vertices int
    edges    []struct{ from, to int }
}

func (g *Graph) HasCycle() bool {
    uf := NewUnionFind(g.vertices)
    
    for _, edge := range g.edges {
        if uf.Connected(edge.from, edge.to) {
            return true  // 发现环
        }
        uf.Union(edge.from, edge.to)
    }
    
    return false
}

// 使用示例
func main() {
    graph := &Graph{
        vertices: 5,
        edges: []struct{ from, to int }{
            {0, 1},
            {1, 2},
            {2, 3},
            {3, 4},
            {4, 1},  // 这条边会形成环
        },
    }
    
    if graph.HasCycle() {
        fmt.Println("图中存在环")
    } else {
        fmt.Println("图中不存在环")
    }
}
```

## 性能分析

### 时间复杂度

1. 基本实现：
   - Find操作：O(N)
   - Union操作：O(N)
   - Connected操作：O(N)

2. 路径压缩：
   - 平均情况下接近O(1)
   - 最坏情况仍为O(log N)

3. 按秩合并：
   - 保证树的高度不超过O(log N)
   - 与路径压缩结合使用时，操作的平均时间复杂度接近但不等于O(1)

### 空间复杂度

- 存储父节点数组：O(N)
- 存储秩数组（如果使用按秩合并）：O(N)
- 总体空间复杂度：O(N)

### 优化效果比较

1. 基本实现 vs 路径压缩：
   - 路径压缩显著减少树的高度
   - 大幅提升后续操作的效率
   - 实现简单，收益明显

2. 基本实现 vs 按秩合并：
   - 控制树的增长
   - 避免最坏情况的发生
   - 实现较复杂

3. 两种优化结合：
   - 理论上最优的性能
   - 实际应用中路径压缩的效果更显著

## 总结

1. 特点优势：
   - 实现简单
   - 性能优秀
   - 空间效率高
   - 适用场景广泛

2. 实现考虑：
   - 选择合适的优化策略
   - 注意数组边界检查
   - 考虑并发安全性

3. 应用场景：
   - 网络连接判断
   - 集合管理
   - 图算法辅助
   - 动态连通性问题