最小生成树

最小生成树（MST）是连接图中所有节点的最小权重路径集合。

Prim 算法

概述

Prim 算法从一个起始节点开始，逐步添加权重最小的边来构建生成树。

实现

import heapq

def prim(graph, start):
    mst = []
    visited = {start}
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start].items()]
    heapq.heapify(edges)
    
    while edges:
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            
            for next_neighbor, next_weight in graph[v].items():
                if next_neighbor not in visited:
                    heapq.heappush(edges, (next_weight, v, next_neighbor))
    
    return mst

# 示例图
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 1, 'C': 2}
}

print("Prim 最小生成树:", prim(graph, 'A'))

Kruskal 算法

概述

Kruskal 算法按权重从小到大排序边，依次添加边直到形成生成树。

实现

def kruskal(graph):
    # 获取所有边并排序
    edges = []
    for node in graph:
        for neighbor, weight in graph[node].items():
            edges.append((weight, node, neighbor))
    
    edges.sort()
    
    # 并查集
    parent = {}
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    
    # 初始化父节点
    for node in graph:
        parent[node] = node
    
    mst = []
    for weight, u, v in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))
    
    return mst

# 示例
print("Kruskal 最小生成树:", kruskal(graph))

复杂度分析

算法	时间复杂度	空间复杂度	适用场景
Prim	O(E + V log V)	O(V)	稠密图
Kruskal	O(E log E)	O(E)	稀疏图

应用场景

• 网络布线
• 电路设计
• 聚类分析