图论工具箱：什么活用什么家伙

💡 打个比方

家里有个工具箱，装锤子、螺丝刀、扳手、剪刀。干活的人不看说明书就拿一把乱砸——活是干完了，家具也砸了。算法也一样：图论的「工具箱」里有六个家伙，各自擅长一种活：

🔗 连通性（BFS / DFS）：「这两点通不通？在不在同一块？」——不数距离，只标「到没到过」。🌉 连通全网最便宜（Kruskal / Prim，MST）：「修几条路把所有村连起来、花的钱最少？」——选 n−1 条边。📍 单源最短路（Dijkstra）：「从一个点到所有点，各走多短？」——盖章 + 松弛。🗺️ 全源最短路（Floyd）：「任意两点都要查？」——一张 n×n 大表。

四件活，四件工具，选错工具不是算不出，而是算得慢或者干脆算错：用 BFS 数「跳数」去答「带权最短路」——跳数最少 ≠ 路程最短（上上节课 1→3 的例子：2 跳的 5 比 1 跳的 6 便宜）；用 Dijkstra 去答「连通全网最便宜」——它只关心「从一个点出发的路」，根本不挑边。

选工具的三步：① 看问什么（连通？全网？最短路？）；② 看规模（n 多大、边多少——稀疏还是稠密）；③ 看权（全相等 → BFS；非负 → Dijkstra 可用；可为负 → Floyd）。今天用「4 个村修路 + 配送」和「5 岛图三问」练三遍，把「看题 → 选家伙」练成条件反射。

🖼️ 大图看明白

💻 完整代码：一张图跑 Kruskal + Dijkstra，两个答案对照

// 输入：无（5 岛 7 桥写死，方便对答案）
// 工具 1（Kruskal）：全网最便宜 → 输出选中的桥 + 总造价（答案 14）
// 工具 2（Dijkstra）：1 号岛到各岛最短路 → 输出账本（答案 0 2 5 9 8）
#include <iostream>
using namespace std;

int g[6][6];      // 邻接矩阵：g[i][j] = 桥造价，0 = 没桥
int fa[6];        // Kruskal 的并查集：fa[i] = i 所在「块」的组长
int dist_[6];     // Dijkstra 账本：1 到各岛的最短路
bool done_[6];    // Dijkstra：岛是否已盖章

int find(int x) {                    // 找 x 的组长（顺路把路压平）
    while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
    return x;
}
void unite(int a, int b) { fa[find(a)] = find(b); }  // 两块并成一块

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;
    for (int i = 1; i <= 5; i++) fa[i] = i;

    // ── 工具 1：Kruskal（造价从低到高试，两端不同块就修）──
    //（正式程序先 sort 边；这里造价只有 2..8，直接按造价从小到大试）
    int total = 0, used = 0;
    for (int w = 2; w <= 8; w++)
        for (int u = 1; u <= 5; u++)
            for (int v = u + 1; v <= 5; v++)
                if (g[u][v] == w && find(u) != find(v)) {
                    unite(u, v);
                    total += w; used++;
                    cout << "Kruskal 修 " << u << "-" << v
                         << "（造价 " << w << "）" << endl;
                }
    cout << "MST 总造价 = " << total << "（修了 " << used << " 座桥）" << endl;

    // ── 工具 2：Dijkstra（1 号岛出发，盖章 + 松弛）──
    const int INF = 999999;
    for (int i = 1; i <= 5; i++) { dist_[i] = INF; done_[i] = false; }
    dist_[1] = 0;
    for (int v = 1; v <= 5; v++) if (g[1][v] > 0) dist_[v] = g[1][v];
    for (int round = 1; round <= 5; round++) {
        int u = 0;
        for (int i = 1; i <= 5; i++)
            if (!done_[i] && (u == 0 || dist_[i] < dist_[u])) u = i;
        done_[u] = true;
        for (int v = 1; v <= 5; v++)
            if (g[u][v] > 0 && !done_[v] && dist_[v] > dist_[u] + g[u][v])
                dist_[v] = dist_[u] + g[u][v];
    }
    for (int i = 1; i <= 5; i++)
        cout << "Dijkstra: 1 到 " << i << " = " << dist_[i] << endl;
    return 0;
}
// 运行结果：
// Kruskal 修 1-2（造价 2）
// Kruskal 修 2-3（造价 3）
// Kruskal 修 3-4（造价 4）
// Kruskal 修 4-5（造价 5）
// MST 总造价 = 14（修了 4 座桥）
// Dijkstra: 1 到 1 = 0
// Dijkstra: 1 到 2 = 2
// Dijkstra: 1 到 3 = 5
// Dijkstra: 1 到 4 = 9
// Dijkstra: 1 到 5 = 8
// 同图两工具：14 是「修桥总造价」，0 2 5 9 8 是「1 出发的路长」——别抄串！

✋ 你来试试