构建无向图最小生成树：掌握图论网络优化之道

# 1. 图论基础与最小生成树概念

**1.1 图论基础**

图论是数学的一个分支，用于研究由顶点和边组成的数学结构。顶点表示实体，而边表示实体之间的关系。图论在计算机科学中广泛应用，如网络优化、数据结构和算法设计。

**1.2 最小生成树概念**

最小生成树（MST）是图论中一个重要的概念。给定一个带权重的无向连通图，MST 是图中所有顶点的子集，它连接了图中的所有顶点，并且权重之和最小。MST 在许多实际应用中都有用，例如网络优化和数据结构。

# 2. 最小生成树算法理论

### 2.1 普里姆算法

#### 2.1.1 算法原理

普里姆算法是一种贪心算法，它从图中一个顶点出发，逐步添加边，构建一棵生成树。算法选择权重最小的边，将新的顶点添加到生成树中，直到生成树包含图中所有顶点。

#### 2.1.2 算法流程

1. **初始化：**选择图中一个顶点作为起始点，并将其添加到生成树中。
2. **选择边：**从生成树中选择权重最小的边，并将该边连接的顶点添加到生成树中。
3. **重复步骤 2：**重复步骤 2，直到生成树包含图中所有顶点。

### 2.2 克鲁斯卡尔算法

#### 2.2.1 算法原理

克鲁斯卡尔算法是一种基于集合的算法，它从图中所有边开始，逐步合并边，构建一棵生成树。算法将具有最小权重的边合并到集合中，直到集合中包含图中所有顶点。

#### 2.2.2 算法流程

1. **初始化：**将图中所有边按权重升序排列。
2. **创建集合：**为图中每个顶点创建一个集合。
3. **合并边：**从排列的边中选择权重最小的边，如果该边连接的两个顶点属于不同的集合，则将这两个集合合并。
4. **重复步骤 3：**重复步骤 3，直到所有顶点都属于同一个集合。

### 2.3 算法对比

| 特征 | 普里姆算法 | 克鲁斯卡尔算法 |
|---|---|---|
| 时间复杂度 | O(E log V) | O(E log E) |
| 空间复杂度 | O(V) | O(E) |
| 适用性 | 适用于稠密图 | 适用于稀疏图 |
| 贪心性 | 是 | 否 |

**代码示例：**

# 普里姆算法
def prim(graph, start):
    # 初始化
    visited = set([start])
    mst = []
    total_weight = 0

    # 循环，直到访问所有顶点
    while len(visited) < len(graph):
        # 寻找权重最小的边
        min_edge = None
        for v in visited:
            for u in graph[v]:
                if u not in visited and (min_edge is None or graph[v][u] < graph[min_edge[0]][min_edge[1]]):
                    min_edge = (v, u)

        # 添加边到生成树中
        visited.add(min_edge[1])
        mst.append(min_edge)
        total_weight += graph[min_edge[0]][min_edge[1]]

    return mst, total_weight

# 克鲁斯卡尔算法
def kruskal(graph):
    # 初始化
    edges = []
    for v in graph:
        for u in graph[v]:
            if u > v:
                edges.append((v, u, graph[v][u]))

    edges.sort(key=lambda x: x[2])

    # 创建集合
    sets = {}
    for v in graph:
        sets[v] = set([v])

    #