Kruskal 是「按桥挑」，Prim 是「从一点往外长」：先占住自家岛，每轮把「连出去最便宜」的新岛接进来——像藤蔓一样，一棵树慢慢长满全图。
上一课 Kruskal 是「全岛桥队排序，便宜优先逐座修」；Prim 换个视角：你是1 号岛的主人，想把全岛都连进自家网络。规则很简单：每轮，在所有「树里 ↔ 树外」的桥里，修最便宜的那一座，把外面的岛接进树里。树里只有一个点、两条边都不算「跨界」——只有一头在树里、一头在树外的桥才考虑。接满 n − 1 座（所有岛都进树）就停。
两种算法像「修路队」和「种田队」：Kruskal 拿着桥的价目表全图挑；Prim 守着已连通的领地一圈圈往外扩。视角不同，但都是贪心，结果一样：都是最小生成树，总造价一样低（具体可能选不同的桥，但总花费相同）。
Prim 需要一张「账本」：dist[i] = 树外的岛 i，接进树最便宜要花多少（即 i 到树里所有点的最短边权）。每接进一个新岛，就用它去「报价」：如果它到某个树外岛更便宜，就更新 dist。每轮干两件事：① 在树外找 dist 最小的点接进来；② 用它更新其余树外点的 dist。
为什么 Prim 也是最优的？同样的换桥论证：每轮接的是「跨界桥里最便宜的」，不接它就得用更贵的桥接同样的岛——贪心不亏。下一课对比两种算法的「账」：稠密图（桥多）Prim 快，稀疏图（桥少）Kruskal 快。
同一道题（5 岛 7 桥），两种贪心视角。先把「两队」的打法摆在一起：
// 同一道题，两种打法（都是贪心，都是最小生成树）： // Kruskal（修路队）： // 把全部桥按造价排序，从便宜到贵逐座看： // 两端「还没通」→ 修；两端「已通」（同组）→ 跳过（会绕圈） // 修满 n − 1 座停。视角：站在「桥」上看。 // 工具：排序 + 同组表（判环）。 // Prim（种田队）： // 先占住自家岛（起点，如 1 号岛），树里只有 1 个点； // 每轮在所有「树里 ↔ 树外」的跨界桥里修最便宜的一座， // 把外面的岛接进树；接满 n − 1 座（全岛进树）停。 // 视角：站在「点」（领地）上看。 // 工具：dist 账本（树外每个岛接进树最便宜花多少）。 // 对照账（同一张 5 岛图）： // Kruskal Prim // 起点 全体桥一起看 从 1 个岛出发 // 每次 挑 1 座桥 接 1 个新岛 // 工具 排序 + 同组表 dist 账本 // 本课 修 2,3,4,5 → 14 接 2,3,4,5 → 14（一样的答案） // 两个都是「最小生成树」：具体选的桥可能不同 //（同价桥时），但总造价一定相同——下一课算「账」比快慢。
还是 5 岛 7 桥。Prim 每轮两件事：① 在树外找 dist 最小的点接进树；② 用新接入的点给其余树外点「报价」（有更便宜的路就更新 dist）。全程手推：
// 5 岛 7 桥：1-2:2 2-3:3 3-4:4 4-5:5 1-3:6 2-4:7 1-5:8 // 起点：1 号岛。dist[i] = 岛 i 接进树的最便宜桥造价 // 初始：树 = {1}。只有 1 在树里，用 1 的桥报价： dist: 2 → 2（经 1-2） 3 → 6（经 1-3） 4 → ∞（1 和 4 没直桥） 5 → 8（经 1-5） // 轮 1：树外 dist 最小 = 2（造价 2）→ 接 2 进树！总 = 2 // 树 = {1, 2}。用新岛 2 报价：2-3:3 < 6 → dist[3] = 3；2-4:7 < ∞ → dist[4] = 7 dist: 3 → 3（经 2-3） 4 → 7（经 2-4） 5 → 8 // 轮 2：树外 dist 最小 = 3（造价 3）→ 接 3 进树！总 = 5 // 树 = {1,2,3}。用新岛 3 报价：3-4:4 < 7 → dist[4] = 4 dist: 4 → 4（经 3-4） 5 → 8 // 轮 3：树外 dist 最小 = 4（造价 4）→ 接 4 进树！总 = 9 // 树 = {1,2,3,4}。用新岛 4 报价：4-5:5 < 8 → dist[5] = 5 dist: 5 → 5（经 4-5） // 轮 4：树外 dist 最小 = 5（造价 5）→ 接 5 进树！总 = 14 // 树 = {1,2,3,4,5} → 全岛进树，完成！ // 结果：依次接入 1-2(2)、2-3(3)、3-4(4)、4-5(5)，总造价 14 // 和 Kruskal 选了同样的 4 座桥、同样的总造价 ✓（本图桥价各不相同）
把手推过程翻译成代码。两张表分工：in[i] = 点 i 是否已在树里（内/外标记）；dist[i] = 树外点 i 接进树的最便宜边权（账本）。邻接矩阵 g[i][j] 存桥造价（0 = 没桥）：
// Prim 核心循环（5 点，邻接矩阵 g；INF = 999 表示「暂时无桥可接」） // in[i]：点 i 在不在树里；dist[i]：树外点 i 接进树最便宜花多少 in[1] = true; dist[1] = 0; // 起点 1 在树里，接入成本 0 for (v = 1..5) if (g[1][v] > 0) dist[v] = g[1][v]; // 初始报价：只有 1 能报价 // 此时 dist = [0, 2, 6, INF, 8]，和手推初始一致 for (轮 = 2..5) { // 还要接 4 个点 // ① 树外找 dist 最小的点 u u = 0; for (i = 1..5) if (!in[i] && (u == 0 || dist[i] < dist[u])) u = i; in[u] = true; total += dist[u]; // 接入成本记账 // ② 新点 u 给其余树外点报价（更便宜才更新） for (v = 1..5) if (!in[v] && g[u][v] > 0 && g[u][v] < dist[v]) dist[v] = g[u][v]; } // 运行轨迹（u = 每轮接入的点）： // 轮 2：u = 2（dist 2）→ dist[3]=3, dist[4]=7 // 轮 3：u = 3（dist 3）→ dist[4]=4 // 轮 4：u = 4（dist 4）→ dist[5]=5 // 轮 5：u = 5（dist 5）→ 完成，total = 14 ✓ 和手推一致
!in[i] 条件——会把树里的点（dist 可能很小）也选进来，同一个岛接两次！选 u 的条件永远是：树外 + dist 最小。两种算法都快，但快的场景不一样。先把「账」算出来：
// Prim（邻接矩阵版）要多久？ // n − 1 轮，每轮：找最小扫 n 个点 + 报价扫 n 个点 → 每轮 O(n) // 总计 O(n²)——只和点数有关，和边数 m 无关（矩阵里 0 也扫） // Kruskal 要多久？ // 排序 m 条边 O(m log m) + 逐条扫 O(m) → O(m log m) // 只和边数有关，和点数关系小 // 对账 1：稠密图（桥多）——n = 50，m = 1225（完全图，任意两岛都有桥） // Prim：n² = 2500 步 // Kruskal：m log m ≈ 1225 × 10.3 ≈ 12600 步 → Prim 快约 5 倍 // 对账 2：稀疏图（桥少）——n = 1000，m = 1500（每岛平均才 3 座桥） // Prim：n² = 1000000 步 // Kruskal：m log m ≈ 1500 × 10.6 ≈ 15900 步 → Kruskal 快约 60 倍 // 口诀：图「稠密」（m 接近 n²/2）→ Prim； // 图「稀疏」（m 接近 n）→ Kruskal。 // （还有「优先队列版 Prim」，稀疏也快——那是更高级的课。）
// 输入：无（5 岛 7 桥写死，方便对答案） // 输出：每轮接入的点 + 用的桥 + 总造价 // 答案：接 2(1-2,2) 3(2-3,3) 4(3-4,4) 5(4-5,5)，总造价 = 14 #include <iostream> using namespace std; int g[6][6]; // 邻接矩阵：g[i][j] = 桥造价，0 = 没桥 int dist_[6]; // 树外点 i 接进树的最便宜边权 bool in[6]; // 点 i 是否已在树里 int main() { // 5 岛 7 桥：1-2:2 2-3:3 3-4:4 4-5:5 1-3:6 2-4:7 1-5:8 g[1][2] = g[2][1] = 2; g[2][3] = g[3][2] = 3; g[3][4] = g[4][3] = 4; g[4][5] = g[5][4] = 5; g[1][3] = g[3][1] = 6; g[2][4] = g[4][2] = 7; g[1][5] = g[5][1] = 8; const int INF = 999; for (int i = 1; i <= 5; i++) { dist_[i] = INF; in[i] = false; } in[1] = true; dist_[1] = 0; for (int v = 1; v <= 5; v++) // 初始报价：只有 1 在树里 if (g[1][v] > 0) dist_[v] = g[1][v]; int total = 0; for (int round = 2; round <= 5; round++) { // 还要接 4 个点 // ① 树外找 dist 最小的点 u int u = 0; for (int i = 1; i <= 5; i++) if (!in[i] && (u == 0 || dist_[i] < dist_[u])) u = i; in[u] = true; total += dist_[u]; // 找出 u 是「经哪座桥」接进来的（在树里、造价 = dist_[u] 的邻居） for (int p = 1; p <= 5; p++) if (in[p] && g[p][u] == dist_[u]) cout << "接入 " << u << "（经桥 " << p << "-" << u << "，造价 " << dist_[u] << "）" << endl; // ② 新点 u 给树外点报价（更便宜才更新） for (int v = 1; v <= 5; v++) if (!in[v] && g[u][v] > 0 && g[u][v] < dist_[v]) dist_[v] = g[u][v]; } cout << "总造价 = " << total << endl; return 0; } // 运行结果：接入 2(1-2,2) 3(2-3,3) 4(3-4,4) 5(4-5,5) → 总造价 = 14 // 把 g[4][5] 改成 9：接入顺序变为 2、3、4、5（经 1-5,8）→ 总造价 = 17
dist_[i] < dist_[u] 严格小于，后面的同值不替换。答案对：同价都是最便宜跨界桥，选谁都不亏（总造价相同，只是树形状可能不同）。