Kruskal算法 - 元素码农

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

↑

# Kruskal算法

Kruskal算法是一种用于寻找加权无向图的最小生成树的贪心算法。本文将详细介绍Kruskal算法的原理、实现和应用。

## 基本概念

### 最小生成树

最小生成树（Minimum Spanning Tree，MST）是一个连通无向图的一个子图，它包含图中的所有顶点，并且是一棵权值和最小的树。

### 算法适用条件

1. 无向图
2. 边权重为非负数
3. 图可以是连通或非连通的
4. 适用于稀疏图

## 算法原理

### 核心思想

Kruskal算法使用贪心策略，按照边的权重从小到大的顺序选择边，如果加入该边不会形成环，则将其加入生成树。算法使用并查集来判断是否形成环。

### 算法步骤

1. 初始化：
   - 将所有边按权重排序
   - 创建并查集，每个顶点作为一个集合

2. 主循环：
   - 按权重从小到大遍历边
   - 如果边的两个顶点不在同一个集合中
   - 将边加入生成树
   - 合并两个顶点的集合

3. 重复步骤2直到选择了V-1条边（V为顶点数）

## 代码实现

### 并查集实现

```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) {
    px, py := uf.Find(x), uf.Find(y)
    if px == py {
        return
    }
    
    // 按秩合并
    if uf.rank[px] < uf.rank[py] {
        uf.parent[px] = py
    } else if uf.rank[px] > uf.rank[py] {
        uf.parent[py] = px
    } else {
        uf.parent[py] = px
        uf.rank[px]++
    }
}

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

### 基本实现

```go
type Edge struct {
    from   int
    to     int
    weight int
}

type Graph struct {
    vertices int
    edges    []Edge
}

func NewGraph(v int) *Graph {
    return &Graph{
        vertices: v,
        edges:    make([]Edge, 0),
    }
}

func (g *Graph) AddEdge(from, to, weight int) {
    g.edges = append(g.edges, Edge{from: from, to: to, weight: weight})
}

func (g *Graph) Kruskal() ([]Edge, int) {
    // 对边按权重排序
    sort.Slice(g.edges, func(i, j int) bool {
        return g.edges[i].weight < g.edges[j].weight
    })
    
    // 初始化并查集
    uf := NewUnionFind(g.vertices)
    
    // 存储最小生成树的边
    mst := make([]Edge, 0, g.vertices-1)
    totalWeight := 0
    
    // 遍历所有边
    for _, edge := range g.edges {
        if !uf.Connected(edge.from, edge.to) {
            uf.Union(edge.from, edge.to)
            mst = append(mst, edge)
            totalWeight += edge.weight
            
            // 如果已经选择了V-1条边，提前结束
            if len(mst) == g.vertices-1 {
                break
            }
        }
    }
    
    return mst, totalWeight
}
```

### 优化实现

```go
type Graph struct {
    vertices int
    edges    []Edge
    // 使用邻接表存储图结构
    adj      []map[int]int
}

func NewGraph(v int) *Graph {
    adj := make([]map[int]int, v)
    for i := range adj {
        adj[i] = make(map[int]int)
    }
    
    return &Graph{
        vertices: v,
        edges:    make([]Edge, 0),
        adj:      adj,
    }
}

func (g *Graph) AddEdge(from, to, weight int) {
    // 无向图需要添加两条边
    g.edges = append(g.edges, Edge{from: from, to: to, weight: weight})
    g.adj[from][to] = weight
    g.adj[to][from] = weight
}

func (g *Graph) KruskalOptimized() ([]Edge, int) {
    // 使用堆来维护边的顺序
    edges := make([]Edge, len(g.edges))
    copy(edges, g.edges)
    heap.Init(&EdgeHeap{edges: edges})
    
    uf := NewUnionFind(g.vertices)
    mst := make([]Edge, 0, g.vertices-1)
    totalWeight := 0
    
    for len(edges) > 0 && len(mst) < g.vertices-1 {
        edge := heap.Pop(&EdgeHeap{edges: edges}).(Edge)
        if !uf.Connected(edge.from, edge.to) {
            uf.Union(edge.from, edge.to)
            mst = append(mst, edge)
            totalWeight += edge.weight
        }
    }
    
    return mst, totalWeight
}

// 边的最小堆实现
type EdgeHeap struct {
    edges []Edge
}

func (h EdgeHeap) Len() int { return len(h.edges) }
func (h EdgeHeap) Less(i, j int) bool { return h.edges[i].weight < h.edges[j].weight }
func (h EdgeHeap) Swap(i, j int) { h.edges[i], h.edges[j] = h.edges[j], h.edges[i] }
func (h *EdgeHeap) Push(x interface{}) { h.edges = append(h.edges, x.(Edge)) }
func (h *EdgeHeap) Pop() interface{} {
    old := h.edges
    n := len(old)
    x := old[n-1]
    h.edges = old[0 : n-1]
    return x
}
```

## 应用示例

### 网络布线

```go
type Location struct {
    id   int
    name string
    x, y float64
}

type NetworkPlanner struct {
    locations []Location
    graph     *Graph
}

func NewNetworkPlanner(locations []Location) *NetworkPlanner {
    n := len(locations)
    planner := &NetworkPlanner{
        locations: locations,
        graph:     NewGraph(n),
    }
    
    // 构建完全图
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            // 计算两点间距离作为权重
            dx := locations[i].x - locations[j].x
            dy := locations[i].y - locations[j].y
            weight := int(math.Sqrt(dx*dx + dy*dy))
            planner.graph.AddEdge(i, j, weight)
        }
    }
    
    return planner
}

func (np *NetworkPlanner) GetOptimalLayout() ([]struct {
    from, to string
    cost    int
}, int) {
    // 使用Kruskal算法获取最小生成树
    edges, totalCost := np.graph.Kruskal()
    
    // 转换结果为可读格式
    layout := make([]struct {
        from, to string
        cost    int
    }, len(edges))
    
    for i, edge := range edges {
        layout[i] = struct {
            from, to string
            cost    int
        }{
            from: np.locations[edge.from].name,
            to:   np.locations[edge.to].name,
            cost: edge.weight,
        }
    }
    
    return layout, totalCost
}
```

### 电路设计

```go
type Component struct {
    id       int
    name     string
    position struct{ x, y float64 }
    voltage  float64
}

type CircuitDesigner struct {
    components []Component
    graph      *Graph
}

func (cd *CircuitDesigner) AddComponent(comp Component) {
    cd.components = append(cd.components, comp)
    
    // 更新图结构
    n := len(cd.components)
    if cd.graph == nil {
        cd.graph = NewGraph(n)
    } else {
        // 扩展图
        newGraph := NewGraph(n)
        // 复制原有边
        for i := 0; i < n-1; i++ {
            for j := i + 1; j < n-1; j++ {
                if weight, ok := cd.graph.adj[i][j]; ok {
                    newGraph.AddEdge(i, j, weight)
                }
            }
        }
        cd.graph = newGraph
    }
    
    // 添加新组件与其他组件的连接
    for i := 0; i < n-1; i++ {
        weight := cd.calculateConnectionCost(cd.components[i], comp)
        cd.graph.AddEdge(i, n-1, weight)
    }
}

func (cd *CircuitDesigner) GetOptimalWiring() ([]struct {
    from, to string
    length  float64
}, float64) {
    edges, totalLength := cd.graph.Kruskal()
    
    wiring := make([]struct {
        from, to string
        length  float64
    }, len(edges))
    
    for i, edge := range edges {
        wiring[i] = struct {
            from, to string
            length  float64
        }{
            from:   cd.components[edge.from].name,
            to:     cd.components[edge.to].name,
            length: float64(edge.weight) / 100, // 转换为实际长度
        }
    }
    
    return wiring, float64(totalLength) / 100
}
```

## 性能分析

### 时间复杂度

1. 基本实现：
   - 边排序：O(E log E)
   - 并查集操作：O(α(V))，其中α是阿克曼函数的反函数
   - 总体复杂度：O(E log E)

2. 优化实现：
   - 使用堆：O(E log E)
   - 并查集操作：O(α(V))
   - 总体复杂度：O(E log E)

### 空间复杂度

1. 基本实现：
   - 边数组：O(E)
   - 并查集：O(V)
   - 总体复杂度：O(E + V)

2. 优化实现：
   - 邻接表：O(V + E)
   - 堆：O(E)
   - 并查集：O(V)
   - 总体复杂度：O(V + E)

### 优化建议

1. 数据结构选择：
   - 稀疏图使用邻接表
   - 稠密图使用邻接矩阵
   - 考虑使用斐波那契堆

2. 实现优化：
   - 并查集路径压缩
   - 预排序优化
   - 剪枝优化

## 总结

1. 算法特点：
   - 贪心策略
   - 适用于稀疏图
   - 实现简单
   - 可处理非连通图

2. 实现考虑：
   - 选择合适的数据结构
   - 注意并查集的优化
   - 考虑实际应用场景

3. 应用领域：
   - 网络布线
   - 电路设计
   - 管道铺设
   - 交通规划