最小生成树：5 个岛修最便宜的桥

💡 打个比方

海上有 5 个岛（图里的「点」），有些岛对之间能修桥（「边」），每座桥造价不同（边的「权」）。目标是：让所有岛都能互相到达，花的钱最少。

先想清楚要修几座：5 个岛，一座一座连——1 座连 2 个岛、2 座连 3 个岛、4 座连 5 个岛。规律：n 个岛最少要 n − 1 座桥。少一座，有岛「孤零零」连不上；多一座，必然出现绕圈（A→B→C→A），圈上的某座桥就是白花钱——去掉它，岛还是全通的。

所以最优方案一定长这样：恰好 n − 1 座桥、全岛连通、不绕圈——这叫生成树（n 个点 n−1 条边的连通图，形似一棵树，没有环）；在所有生成树里总造价最小的，就是最小生成树。

怎么找到它？Kruskal 算法（克拉斯卡尔，1956 年）：把所有桥按造价从便宜到贵排序，然后一条一条看：这座桥连的两个岛如果还不通（不同组）就修；如果已经通了（同组，再修就绕圈）就跳过。修满 n − 1 座就停。就这么简单——便宜优先，绝不绕圈！

🖼️ 大图看明白

💻 完整代码：5 岛 7 桥 Kruskal（同组表判环 + 排序 + 修满 n−1 停）

// 输入：无（5 岛 7 桥直接写死在程序里，方便对答案）
// 输出：每座「修的桥 / 跳过的桥」+ 总造价
// 答案：修 1-2、2-3、3-4、4-5，总造价 = 14
#include <iostream>
#include <algorithm>
using namespace std;

struct Edge { int u, v, w; };   // 一座桥：两端 u、v，造价 w
Edge e[7];
int grp[5];                     // 同组表：grp[i] = 岛 i+1 的组号

bool byW(const Edge &a, const Edge &b) { return a.w < b.w; }
int findGroup(int x) { return grp[x - 1]; }
void unionGroup(int a, int b) {
    int ga = grp[a - 1], gb = grp[b - 1];
    for (int i = 0; i < 5; i++)
        if (grp[i] == gb) grp[i] = ga;   // b 的组并入 a 的组
}

int main() {
    // 候选桥：1-2:2  2-3:3  3-4:4  4-5:5  1-3:6  2-4:7  1-5:8
    e[0] = {1, 2, 2};  e[1] = {2, 3, 3};  e[2] = {3, 4, 4};
    e[3] = {4, 5, 5};  e[4] = {1, 3, 6};  e[5] = {2, 4, 7};
    e[6] = {1, 5, 8};

    for (int i = 0; i < 5; i++) grp[i] = i + 1;   // 初始：各岛自己一组

    sort(e, e + 7, byW);          // 第 1 步：按造价排序（便宜 → 贵）

    int cnt = 0, total = 0;
    for (int i = 0; i < 7 && cnt < 4; i++) {      // 修满 5 − 1 = 4 座就停
        if (findGroup(e[i].u) != findGroup(e[i].v)) {
            cout << "修桥 " << e[i].u << "-" << e[i].v
                 << "（造价 " << e[i].w << "）" << endl;
            unionGroup(e[i].u, e[i].v);          // 修桥 → 立刻合并
            cnt++;
            total += e[i].w;
        } else {
            cout << "跳过 " << e[i].u << "-" << e[i].v
                 << "（已同组，会绕圈）" << endl;
        }
    }
    cout << "总造价 = " << total << endl;
    return 0;
}
// 运行结果：修 1-2(2) 2-3(3) 3-4(4) 4-5(5) → 总造价 = 14
// 把 e[3] 改成 {4,5,9} 再跑：修 1-2、2-3、3-4、1-5 → 总造价 = 17

✋ 你来试试