本课时有配套视频讲解，购买后即可观看（永久有效）

Prim求最小生成树

一、课上练习

编程练习

最小生成树(Prim1)：L49975

二、知识总结

✨ 核心思想

Prim 算法是一种贪心算法，用于求无向连通图的最小生成树（Minimum Spanning Tree，MST）。核心思想是：从任意一个顶点开始，每次从已选顶点集合向外扩展，选择连接已选集合和未选集合的最小权边，将对应顶点加入集合。重复 n-1 次，即得到最小生成树。

✨ 算法原理

最小生成树的定义： 给定无向连通图 G=(V, E)，生成树是包含所有顶点的无环连通子图。最小生成树是所有生成树中边权和最小的那棵。

Prim 算法流程：

初始化：选择任意顶点 s 加入集合 S，其余顶点在集合 V-S 中
维护数组 dist[v]：表示 v 到集合 S 中顶点的最小边权
每次从 V-S 中选出 dist[v] 最小的顶点 v，加入 S
将 v 加入 S 后，更新 V-S 中所有顶点的 dist 值
重复步骤 3-4，共 n-1 次

正确性证明（切割性质）： 对于图的任意切割（将顶点分成两个集合），跨越切割的最小权边一定属于某棵最小生成树。Prim 算法每次选择的边恰好是跨越 (S, V-S) 切割的最小权边。

与 Dijkstra 的相似性： Prim 和 Dijkstra 算法结构非常相似，区别在于：

Dijkstra：dist[v] = 源点到 v 的最短路径长度
Prim：dist[v] = v 到已选集合的最小边权

✨ 代码实现

1#include <iostream>
2#include <cstring>
3using namespace std;
4
5const int MAXN = 5005;
6const int INF = 0x3f3f3f3f;
7
8int g[MAXN][MAXN]; // 邻接矩阵
9int dist[MAXN];    // 到已选集合的最小边权
10bool inMST[MAXN];  // 是否已加入MST
11int n, m;
12
13// Prim算法，返回MST的总权值
14// 如果图不连通返回-1
15long long prim() {
16    // 初始化
17    memset(dist, 0x3f, sizeof(dist));
18    memset(inMST, false, sizeof(inMST));
19
20    dist[1] = 0; // 从顶点1开始
21    long long totalWeight = 0;
22
23    for (int i = 0; i < n; i++) {
24        // 从未选顶点中找dist最小的
25        int u = -1;
26        for (int j = 1; j <= n; j++) {
27            if (!inMST[j] && (u == -1 || dist[j] < dist[u])) {
28                u = j;
29            }
30        }
31
32        // 图不连通
33        if (dist[u] == INF) return -1;
34
35        // 将u加入MST
36        inMST[u] = true;
37        totalWeight += dist[u];
38
39        // 更新与u相邻的未选顶点的dist
40        for (int v = 1; v <= n; v++) {
41            if (!inMST[v] && g[u][v] < dist[v]) {
42                dist[v] = g[u][v];
43            }
44        }
45    }
46
47    return totalWeight;
48}
49
50int main() {
51    ios::sync_with_stdio(false);
52    cin.tie(nullptr);
53
54    cin >> n >> m;
55
56    // 初始化邻接矩阵
57    memset(g, 0x3f, sizeof(g));
58    for (int i = 1; i <= n; i++) g[i][i] = 0;
59
60    for (int i = 0; i < m; i++) {
61        int u, v, w;
62        cin >> u >> v >> w;
63        // 处理重边：保留最小的
64        g[u][v] = min(g[u][v], w);
65        g[v][u] = min(g[v][u], w);
66    }
67
68    long long ans = prim();
69    if (ans == -1) {
70        cout << "图不连通，无法生成MST" << endl;
71    } else {
72        cout << ans << endl;
73    }
74
75    return 0;
76}

1#include <iostream>
2#include <cstring>
3#include <vector>
4using namespace std;
5
6const int MAXN = 5005;
7const int INF = 0x3f3f3f3f;
8
9int g[MAXN][MAXN];
10int dist[MAXN];
11bool inMST[MAXN];
12int from[MAXN]; // 记录每个节点是从哪个节点连过来的
13int n, m;
14
15struct Edge {
16    int u, v, w;
17};
18
19// Prim算法，同时记录MST的边
20pair<long long, vector<Edge>> primWithEdges() {
21    memset(dist, 0x3f, sizeof(dist));
22    memset(inMST, false, sizeof(inMST));
23    memset(from, -1, sizeof(from));
24
25    dist[1] = 0;
26    long long totalWeight = 0;
27    vector<Edge> mstEdges;
28
29    for (int i = 0; i < n; i++) {
30        int u = -1;
31        for (int j = 1; j <= n; j++) {
32            if (!inMST[j] && (u == -1 || dist[j] < dist[u]))
33                u = j;
34        }
35
36        if (dist[u] == INF) return {-1, {}};
37
38        inMST[u] = true;
39        totalWeight += dist[u];
40
41        // 记录边（跳过起始节点）
42        if (from[u] != -1) {
43            mstEdges.push_back({from[u], u, dist[u]});
44        }
45
46        for (int v = 1; v <= n; v++) {
47            if (!inMST[v] && g[u][v] < dist[v]) {
48                dist[v] = g[u][v];
49                from[v] = u; // 记录v是从u连过来的
50            }
51        }
52    }
53
54    return {totalWeight, mstEdges};
55}
56
57int main() {
58    ios::sync_with_stdio(false);
59    cin.tie(nullptr);
60
61    cin >> n >> m;
62    memset(g, 0x3f, sizeof(g));
63
64    for (int i = 0; i < m; i++) {
65        int u, v, w;
66        cin >> u >> v >> w;
67        g[u][v] = min(g[u][v], w);
68        g[v][u] = min(g[v][u], w);
69    }
70
71    auto [weight, edges] = primWithEdges();
72    if (weight == -1) {
73        cout << "图不连通" << endl;
74    } else {
75        cout << "MST总权值：" << weight << endl;
76        cout << "MST的边：" << endl;
77        for (auto& e : edges) {
78            cout << e.u << " - " << e.v
79                 << " (权值" << e.w << ")" << endl;
80        }
81    }
82
83    return 0;
84}

✨ 执行示例

以下面的图为例（5 个顶点，7 条边）：

1    1 ---2--- 2
2    |  \      |
3    3   8     5
4    |    \    |
5    3 ---7--- 4
6     \       /
7      9    6
8       \ /
9        5

边：(1,2,2), (1,3,3), (1,4,8), (2,4,5), (3,4,7), (3,5,9), (4,5,6)

Prim 执行过程（从顶点 1 开始）：

1初始: S={}, dist=[INF,0,INF,INF,INF,INF]
2
3第1轮: 选顶点1(dist=0), S={1}
4  更新: dist[2]=min(INF,2)=2, dist[3]=min(INF,3)=3, dist[4]=min(INF,8)=8
5  dist=[0, 2, 3, 8, INF]
6
7第2轮: 选顶点2(dist=2), S={1,2}
8  更新: dist[4]=min(8,5)=5
9  dist=[0, 2, 3, 5, INF]
10  选边: 1-2(权2)
11
12第3轮: 选顶点3(dist=3), S={1,2,3}
13  更新: dist[4]=min(5,7)=5(不变), dist[5]=min(INF,9)=9
14  dist=[0, 2, 3, 5, 9]
15  选边: 1-3(权3)
16
17第4轮: 选顶点4(dist=5), S={1,2,3,4}
18  更新: dist[5]=min(9,6)=6
19  dist=[0, 2, 3, 5, 6]
20  选边: 2-4(权5)
21
22第5轮: 选顶点5(dist=6), S={1,2,3,4,5}
23  选边: 4-5(权6)
24
25MST总权值 = 0+2+3+5+6 = 16
26MST的边: (1,2), (1,3), (2,4), (4,5)

✨ 解题步骤详解

读入图：构建邻接矩阵（注意处理重边，保留权值最小的）
初始化：dist 全设为 INF，起始点 dist 为 0
主循环 n 次：每次选 dist 最小的未选顶点
更新 dist：新加入顶点的邻居可能获得更小的连接边权
判断连通性：如果某次选出的顶点 dist 为 INF，说明图不连通

Prim vs Kruskal：

Prim O(V²)：适合稠密图（邻接矩阵存储）
Kruskal O(E log E)：适合稀疏图（边集存储）
堆优化 Prim O(E log V)：适合任何图

✨ 常见错误

邻接矩阵初始化错误：应初始化为 INF，不是 0
重边处理遗漏：同一对顶点可能有多条边，应保留权值最小的
自环未处理：g[i][i] 应为 0 或不参与 MST
dist 数组含义混淆：Prim 的 dist 是到集合的最小边权，不是到源点的最短路
不判断连通性：图不连通时无法生成 MST，需要检测
起始点的 dist 值被计入总权值：起始点 dist=0，不影响结果，但要注意

✨ 算法评价

指标	值
时间复杂度	O(V²)（邻接矩阵实现）
空间复杂度	O(V²)（邻接矩阵）
适用场景	稠密图（边数接近 V²）

朴素 Prim 算法的 O(V²) 复杂度在稠密图中是最优的，因为仅读入所有边就需要 O(E) = O(V²) 的时间。对于稀疏图，应使用堆优化版本将复杂度降低到 O(E log V)。

三、课后练习

编程练习

最优布线问题：T1349