最小生成树——Prim 算法
Prim 算法同样用于求解无向连通带权图的最小生成树。
与 Kruskal 算法按照边的权值进行选择不同,Prim 算法从某个顶点出发,不断选择一条权值最小的边,将新的顶点加入当前生成树,直到所有顶点都被加入。
Prim 算法也是一种贪心算法。
一、算法思路
首先选择一个顶点作为起点,将它加入最小生成树。
然后在所有尚未加入的顶点中,寻找与当前生成树连接权值最小的顶点,将它加入生成树,并更新其他顶点到生成树的最小距离。
重复以上操作,直到全部顶点被加入。
这里使用邻接矩阵存储图,并通过两个数组记录算法运行时的状态:
dis[]:记录每个顶点到当前生成树的最小连接权值。vis[]:记录顶点是否已经加入生成树。
每次从未访问的顶点中选择 dis 最小的一个,然后更新距离。
二、代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 6000;
const int inf = 9999;
bool vis[maxn];
int n, m, sum = 0, dis[maxn], maps[maxn][maxn];
void Prim() {
for (int i = 1; i <= n; i++)
dis[i] = maps[1][i];
vis[1] = 1;
for (int i = 1; i <= n - 1; i++)
{
int minn,pos;
minn = inf;
for (int j = 1; j <= n; j++)
{
if (vis[j] == 0 && dis[j] < minn)
{
minn = dis[j];
pos = j;
}
}
vis[pos] = 1;
sum += dis[pos];
for (int j = 1; j <= n; j++)
{
if (vis[j] == 0 && maps[pos][j] < dis[j])
dis[j] = maps[pos][j];
}
}
}
void init() {
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
maps[i][j] = inf;
else
maps[i][j] = 0;
}
}
}
int main() {
int minIndex;
cin >> n >> m;
init();
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
maps[x][y] = min(maps[x][y],z);
maps[y][x] = min(maps[y][x],z);
}
Prim();
cout << sum << endl;
return 0;
}
三、代码分析
首先使用 maps[][] 邻接矩阵保存图。
在 init() 函数中,将不同顶点之间的初始距离设为 inf,顶点到自身的距离设为 0。
if (i != j)
maps[i][j] = inf;
else
maps[i][j] = 0;
输入边时,由于这里处理的是无向图,所以需要同时更新两个方向:
maps[x][y] = min(maps[x][y],z);
maps[y][x] = min(maps[y][x],z);
使用 min() 可以在两个顶点之间存在多条边时,保留权值较小的一条边。
在 Prim() 函数中,选择 1 号顶点作为起点:
for (int i = 1; i <= n; i++)
dis[i] = maps[1][i];
vis[1] = 1;
初始时,dis[i] 表示顶点 1 到顶点 i 的连接权值。
随后遍历所有尚未加入生成树的顶点,从中寻找 dis 最小的顶点:
if (vis[j] == 0 && dis[j] < minn)
{
minn = dis[j];
pos = j;
}
找到之后,将该顶点标记为已访问,并将对应的边权加入总权值:
vis[pos] = 1;
sum += dis[pos];
因为生成树中增加了一个新的顶点,所以其他顶点到生成树的最小连接权值也可能发生变化。
通过下面的代码进行更新:
if (vis[j] == 0 && maps[pos][j] < dis[j])
dis[j] = maps[pos][j];
这样就完成了一次顶点的加入和距离更新。
整个过程需要执行 $n-1$ 次,最终输出 sum,即最小生成树的权值之和。
四、时间复杂度
当前程序使用邻接矩阵存储图。
在 Prim 算法中,每次选择新的顶点,都需要遍历所有顶点,寻找最小的 dis 值。加入顶点之后,还需要再次遍历其他顶点以更新距离。
因此,当前实现的时间复杂度为:
其中 $n$ 为图的顶点数。
Kruskal 算法主要通过排序选择边,而 Prim 算法通过不断扩展已有的生成树来选择顶点。
两者都可以用于求解最小生成树,只是采用了不同的实现方法。

















最扎眼的应该是 `const int inf = 9999`。当年随手定义了一个无穷大,实际上只要边权达到 9999,就可能出现找不到下一个顶点的情况。
更离谱的是 `int minn,pos;`,其中 `pos` 根本没有初始化。如果图不连通,或者所有候选边权都不小于 `inf`,程序就可能直接拿一个未初始化的变量去访问数组,属于未定义行为。
还有 `maps[6000][6000]` 这个邻接矩阵,光是它就占了大约 144 MB 内存。对于稀疏图,这种存储方式显然不太合适。而且数组下标从 1 开始使用,如果 `n` 真等于 6000,还会发生越界。
`main()` 里面甚至留了一个完全没有使用的 `minIndex`,估计是写到一半改过思路,最后也没清理。
不过算法的主体逻辑倒是没有写错。通过 `dis[]` 维护当前生成树到其他顶点的最小连接权值,再不断加入新的顶点,确实是朴素 Prim 的正常实现。
没有更多啦