xxx 最小生成树的 Jarník-Prim 算法
字数 2309 2025-11-12 19:08:29

xxx 最小生成树的 Jarník-Prim 算法

题目描述
给定一个连通无向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有一个权重 \(w(e)\)。要求构造一棵生成树，使得树上所有边的权重之和最小。这类问题称为最小生成树（Minimum Spanning Tree, MST）问题。Jarník-Prim 算法（常称为 Prim 算法）通过贪心策略逐步扩展生成树，从任意一个顶点开始，每次选择连接当前生成树与剩余顶点集合的最小权重边，直到所有顶点都被包含在生成树中。

解题过程循序渐进讲解

步骤 1：算法基本思想
Prim 算法的核心思想是维护两个顶点集合：

  • 树内顶点集合 \(T\): 已加入生成树的顶点。
  • 树外顶点集合 \(V \setminus T\): 尚未加入生成树的顶点。

算法从任意一个顶点开始，初始化 \(T\) 为空。每一步选择一条连接 \(T\) 与 \(V \setminus T\) 的最小权重边 \((u, v)\)，其中 \(u \in T\)，\(v \in V \setminus T\)，并将 \(v\) 加入 \(T\)。重复此过程直到 \(T = V\)。

为什么这是正确的？
该贪心策略基于以下性质（割性质）：对于图的任意割（将顶点分为两个集合），连接这两个集合的最小权重边一定属于某棵最小生成树。Prim 算法在每一步中，当前 \(T\) 与 \(V \setminus T\) 形成一个割，选择的边正是该割的最小权重边，因此最终构造的生成树是最小生成树。

步骤 2：数据结构与初始化
为了高效选择最小权重边，需维护每个树外顶点到树内顶点的最小边权重（距离），并用优先队列（最小堆）快速获取当前最小边。

  1. 输入：

    • 图 \(G = (V, E)\)，用邻接表表示，每个顶点记录其邻接顶点及边权重。
    • 任意选择一个起始顶点 \(s \in V\)。

  2. 初始化：

    • 创建一个数组 key，key[v] 表示顶点 \(v\) 到当前树内顶点的最小边权重。初始化 key[s] = 0，其他顶点的 key 设为 \(\infty\)。
    • 创建一个数组 parent，parent[v] 表示在生成树中 \(v\) 的父顶点（用于记录边）。
    • 创建一个最小堆（优先队列）Q，存储所有顶点，以 key 值为优先级。

步骤 3：算法主循环

  1. 当优先队列 Q 非空时：

    • 从 Q 中弹出 key 值最小的顶点 \(u\)（即当前与树内顶点集合距离最近的树外顶点）。
    • 将 \(u\) 加入树内顶点集合 \(T\)（标记为已访问）。
    • 遍历 \(u\) 的所有邻接顶点 \(v\)：
      • 若 \(v\) 仍在 Q 中（即未加入树）且边 \((u, v)\) 的权重 \(w(u, v) < \text{key}[v]\)：
        • 更新 parent[v] = u。
        • 更新 key[v] = w(u, v)。
        • 调整优先队列中 \(v\) 的优先级。

  2. 循环结束后，parent 数组记录了最小生成树的所有边（除根节点外，每个顶点有其父顶点）。

步骤 4：示例演示
考虑以下无向图（顶点：A, B, C, D；边及权重：A-B:1, A-C:4, B-C:2, B-D:6, C-D:3），以 A 为起点。

  • 初始化：key = [A:0, B:∞, C:∞, D:∞]，parent = [A:null, B:null, C:null, D:null]，Q = {A, B, C, D}。
  • 第 1 步：弹出 A（key=0），遍历邻接点 B 和 C：
    • 更新 B：key[B] = 1，parent[B] = A。
    • 更新 C：key[C] = 4，parent[C] = A。
  • 第 2 步：弹出 B（key=1），遍历邻接点 C 和 D：
    • C：边权重 2 < key[C]=4，更新 key[C] = 2，parent[C] = B。
    • D：更新 key[D] = 6，parent[D] = B。
  • 第 3 步：弹出 C（key=2），遍历邻接点 D：
    • D：边权重 3 < key[D]=6，更新 key[D] = 3，parent[D] = C。
  • 第 4 步：弹出 D（key=3），队列空。

生成树边：A-B, B-C, C-D，总权重 = 1 + 2 + 3 = 6。

步骤 5：复杂度分析

  • 时间复杂度：
    • 使用二叉堆：每次插入和提取最小值为 \(O(\log V)\)，共 \(O(E)\) 次更新操作（每次更新需 \(O(\log V)\)），总复杂度 \(O(E \log V)\)。
    • 使用斐波那契堆：更新操作可降为 \(O(1)\) 摊销时间，总复杂度 \(O(E + V \log V)\)。
  • 空间复杂度：\(O(V + E)\) 存储图及辅助数组。

步骤 6：关键点总结

  1. Prim 算法适用于稠密图（边数接近顶点数平方）时，使用邻接矩阵和简单数组可实现 \(O(V^2)\) 时间，优于 Kruskal 算法。
  2. 算法始终维护当前生成树与剩余顶点间的最小边，保证每一步的局部最优选择导向全局最优解。
  3. 注意处理平行边（取最小权重）和非连通图（算法仅生成连通分量的最小生成树，需额外处理）。
xxx 最小生成树的 Jarník-Prim 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个权重 \( w(e) \)。要求构造一棵生成树，使得树上所有边的权重之和最小。这类问题称为最小生成树（Minimum Spanning Tree, MST）问题。Jarník-Prim 算法（常称为 Prim 算法）通过贪心策略逐步扩展生成树，从任意一个顶点开始，每次选择连接当前生成树与剩余顶点集合的最小权重边，直到所有顶点都被包含在生成树中。 解题过程循序渐进讲解 步骤 1：算法基本思想 Prim 算法的核心思想是维护两个顶点集合： 树内顶点集合 \( T \) : 已加入生成树的顶点。 树外顶点集合 \( V \setminus T \) : 尚未加入生成树的顶点。 算法从任意一个顶点开始，初始化 \( T \) 为空。每一步选择一条连接 \( T \) 与 \( V \setminus T \) 的最小权重边 \( (u, v) \)，其中 \( u \in T \)，\( v \in V \setminus T \)，并将 \( v \) 加入 \( T \)。重复此过程直到 \( T = V \)。 为什么这是正确的？ 该贪心策略基于以下性质（割性质）：对于图的任意割（将顶点分为两个集合），连接这两个集合的最小权重边一定属于某棵最小生成树。Prim 算法在每一步中，当前 \( T \) 与 \( V \setminus T \) 形成一个割，选择的边正是该割的最小权重边，因此最终构造的生成树是最小生成树。 步骤 2：数据结构与初始化 为了高效选择最小权重边，需维护每个树外顶点到树内顶点的最小边权重（距离），并用优先队列（最小堆）快速获取当前最小边。 输入 ： 图 \( G = (V, E) \)，用邻接表表示，每个顶点记录其邻接顶点及边权重。 任意选择一个起始顶点 \( s \in V \)。 初始化 ： 创建一个数组 key ， key[v] 表示顶点 \( v \) 到当前树内顶点的最小边权重。初始化 key[s] = 0 ，其他顶点的 key 设为 \( \infty \)。 创建一个数组 parent ， parent[v] 表示在生成树中 \( v \) 的父顶点（用于记录边）。 创建一个最小堆（优先队列） Q ，存储所有顶点，以 key 值为优先级。 步骤 3：算法主循环 当优先队列 Q 非空时： 从 Q 中弹出 key 值最小的顶点 \( u \)（即当前与树内顶点集合距离最近的树外顶点）。 将 \( u \) 加入树内顶点集合 \( T \)（标记为已访问）。 遍历 \( u \) 的所有邻接顶点 \( v \)： 若 \( v \) 仍在 Q 中（即未加入树）且边 \( (u, v) \) 的权重 \( w(u, v) < \text{key}[ v ] \)： 更新 parent[v] = u 。 更新 key[v] = w(u, v) 。 调整优先队列中 \( v \) 的优先级。 循环结束后， parent 数组记录了最小生成树的所有边（除根节点外，每个顶点有其父顶点）。 步骤 4：示例演示 考虑以下无向图（顶点：A, B, C, D；边及权重：A-B:1, A-C:4, B-C:2, B-D:6, C-D:3），以 A 为起点。 初始化 ： key = [A:0, B:∞, C:∞, D:∞] ， parent = [A:null, B:null, C:null, D:null] ， Q = {A, B, C, D} 。 第 1 步 ：弹出 A（key=0），遍历邻接点 B 和 C： 更新 B： key[B] = 1 ， parent[B] = A 。 更新 C： key[C] = 4 ， parent[C] = A 。 第 2 步 ：弹出 B（key=1），遍历邻接点 C 和 D： C：边权重 2 < key[ C]=4，更新 key[C] = 2 ， parent[C] = B 。 D：更新 key[D] = 6 ， parent[D] = B 。 第 3 步 ：弹出 C（key=2），遍历邻接点 D： D：边权重 3 < key[ D]=6，更新 key[D] = 3 ， parent[D] = C 。 第 4 步 ：弹出 D（key=3），队列空。 生成树边：A-B, B-C, C-D，总权重 = 1 + 2 + 3 = 6。 步骤 5：复杂度分析 时间复杂度 ： 使用二叉堆：每次插入和提取最小值为 \( O(\log V) \)，共 \( O(E) \) 次更新操作（每次更新需 \( O(\log V) \)），总复杂度 \( O(E \log V) \)。 使用斐波那契堆：更新操作可降为 \( O(1) \) 摊销时间，总复杂度 \( O(E + V \log V) \)。 空间复杂度 ：\( O(V + E) \) 存储图及辅助数组。 步骤 6：关键点总结 Prim 算法适用于稠密图（边数接近顶点数平方）时，使用邻接矩阵和简单数组可实现 \( O(V^2) \) 时间，优于 Kruskal 算法。 算法始终维护当前生成树与剩余顶点间的最小边，保证每一步的局部最优选择导向全局最优解。 注意处理平行边（取最小权重）和非连通图（算法仅生成连通分量的最小生成树，需额外处理）。