最小生成树(Minimum Spanning Tree, MST)中的 Prim 算法详解(C语言实现)
1. 什么是最小生成树?
在学习 Prim 算法之前,我们首先需要理解什么是最小生成树(Minimum Spanning Tree,MST)。
1.1 图的基本概念
图(Graph)通常表示为:
\[ G=(V,E) \]其中:
V:顶点集合(Vertex)E:边集合(Edge)
例如:
2
A ------- B
| \ |
6 | \3 | 1
| \ |
C ------- D
4
顶点集合:
V={A,B,C,D}
边集合:
E={(A,B),(A,C),(A,D),(B,D),(C,D)}
如果每条边具有一个权值,那么这个图称为:
带权无向图(Weighted Undirected Graph)
例如:
A-B = 2
A-C = 6
A-D = 3
B-D = 1
C-D = 4
2. 什么是生成树?
对于一个连通图,如果选择其中一部分边,使其满足:
- 包含所有顶点
- 任意两个顶点之间都有路径
- 不存在环
那么得到的子图称为:
生成树(Spanning Tree)
例如:
原图:
A ----- B
| \ |
| \ |
C ----- D
选择:
A-B
A-C
B-D
得到:
A ----- B
|
|
C
B ----- D
满足:
- 所有节点都连接
- 没有环
所以它是一棵生成树。
3. 什么是最小生成树?
一个图可能存在很多棵生成树。
不同生成树的边权值总和不同。
例如:
生成树1
选择:
A-B = 2
B-D = 1
D-C = 4
总权值:
\[ 2+1+4=7 \]生成树2
选择:
A-D = 3
D-B = 1
A-C = 6
总权值:
\[ 3+1+6=10 \]显然:
第一棵树权值更小。
因此:
权值总和最小的生成树称为最小生成树。
4. Prim算法基本思想
Prim算法是一种典型的:
贪心算法(Greedy Algorithm)
它的核心思想:
从任意一个顶点开始,每次选择连接当前生成树和外部节点的最小权值边,将新的节点加入生成树。
可以理解为:
已经加入生成树的节点
|
|
寻找最短边
|
|
加入新的节点
不断重复这个过程,直到所有节点都加入。
5. Prim算法执行过程
假设有如下图:
2
A ------- B
| |
6 | | 1
| |
C ------- D
4
A-D = 3
对应邻接矩阵:
A B C D
A 0 2 6 3
B 2 0 ∞ 1
C 6 ∞ 0 4
D 3 1 4 0
其中:
- 0表示自己到自己
- ∞表示两个节点之间没有直接连接
第一步:选择起点A
当前生成树:
A
已经加入:
U={A}
寻找连接A的最小边:
A-B=2
A-D=3
A-C=6
最小:
A-B=2
加入B。
现在:
U={A,B}
生成树:
A------B
2
第二步:选择D
当前:
已经加入:
A,B
未加入:
C,D
寻找最小边:
A-D=3
A-C=6
B-D=1
最小:
B-D=1
加入D。
现在:
U={A,B,D}
生成树:
A------B
|
|
D
第三步:选择C
剩余节点:
C
连接C的边:
A-C=6
D-C=4
选择:
D-C=4
加入C。
最终:
A------B
|
|
D
|
C
总权值:
\[ 2+1+4=7 \]这就是最小生成树。
6. Prim算法中的三个核心数组
在程序实现中,需要维护三个重要数组:
6.1 visited数组
作用:
判断某个顶点是否已经加入最小生成树。
例如:
visited[i]=1;
表示:
节点i已经加入MST
例如:
节点:
A B C D
visited:
1 1 0 1
表示:
A、B、D已经加入。
6.2 lowcost数组
作用:
保存当前生成树连接每个未加入节点的最小边权值。
例如:
当前:
生成树:
A,B
对于节点:
C:
A-C=6
D:
B-D=1
因此:
lowcost[C]=6
lowcost[D]=1
Prim算法每一步就是:
寻找:
lowcost最小的节点
然后加入。
6.3 parent数组
作用:
记录当前节点由哪个节点连接进来。
例如:
D通过B加入:
parent[D]=B
最终可以得到:
A-B
B-D
D-C
7. Prim算法流程总结
伪代码:
Prim(G)
1. 初始化visited数组
2. 选择一个起点
3. 将起点加入生成树
4. 重复 n-1 次:
找到lowcost最小的节点k
将k加入生成树
更新其它节点的lowcost
5. 输出最小生成树
8. C语言实现(邻接矩阵)
8.1 完整代码
#include<stdio.h>
#define MAX 100
#define INF 999999
void Prim(int graph[MAX][MAX], int n)
{
int visited[MAX]={0};
int lowcost[MAX];
int parent[MAX];
//初始化
for(int i=0;i<n;i++)
{
lowcost[i]=graph[0][i];
parent[i]=0;
}
//默认从0号节点开始
visited[0]=1;
int sum=0;
//加入n-1条边
for(int i=1;i<n;i++)
{
int min=INF;
int k=-1;
//寻找最小边
for(int j=0;j<n;j++)
{
if(!visited[j] && lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
}
//加入节点k
visited[k]=1;
printf("%d -- %d 权值:%d\n",
parent[k],
k,
lowcost[k]);
sum+=lowcost[k];
//更新lowcost
for(int j=0;j<n;j++)
{
if(!visited[j] &&
graph[k][j]<lowcost[j])
{
lowcost[j]=graph[k][j];
parent[j]=k;
}
}
}
printf("最小生成树权值:%d\n",sum);
}
int main()
{
int graph[MAX][MAX]=
{
{0,2,6,3},
{2,0,INF,1},
{6,INF,0,4},
{3,1,4,0}
};
Prim(graph,4);
return 0;
}
9. 代码执行过程分析
初始化:
visited:
A B C D
1 0 0 0
lowcost:
0 2 6 3
第一次:
寻找最小:
B
因为:
lowcost[B]=2
加入:
A-B
更新:
D的距离变成1
第二次:
寻找:
D
因为:
lowcost[D]=1
加入:
B-D
第三次:
寻找:
C
因为:
lowcost[C]=4
加入:
D-C
最终:
A-B 权值2
B-D 权值1
D-C 权值4
总权值:
7
10. Prim算法时间复杂度分析
采用邻接矩阵实现。
每次寻找最小lowcost:
需要:
\[ O(V) \]更新距离:
需要:
\[ O(V) \]总共执行:
\[ V-1 \]所以:
\[ O(V^2) \]因此:
邻接矩阵版本Prim算法时间复杂度为 O(V²)
11. Prim算法与Kruskal算法比较
| Prim算法 | Kruskal算法 | |
|---|---|---|
| 核心思想 | 扩展顶点 | 选择最小边 |
| 策略 | 点驱动 | 边驱动 |
| 主要数据结构 | 邻接矩阵 | 并查集 |
| 适合图 | 稠密图 | 稀疏图 |
| 时间复杂度 | O(V²) | O(ElogE) |
12. 学习Prim算法需要掌握的重点
visited
表示:
哪些节点已经加入MST
lowcost
表示:
当前情况下,
生成树连接外部节点的最短距离
parent
表示:
当前节点由哪个节点连接进入MST
13. 一句话理解Prim算法
Prim算法就是从一个顶点开始,不断寻找距离当前生成树最近的节点,并把它加入生成树,直到所有节点都被连接,最终形成最小生成树。
整个过程:
选择起点
↓
寻找最近节点
↓
加入生成树
↓
更新距离
↓
重复
↓
得到MST