Prim 算法思路介绍
Prim 用于找出一个无向连通图的最小生成树（Minimum Spanning Tree）。首先初始化一个空集 S，然后选择一个起点，加入到 S 中。此后不断选择与 S 中的顶点距离最短的顶点，加入到 S 中，并输出这条最短的边。最终，所有点都将被加入到集合 S 中，而被输出的边就是最小生成树中的所有边。
Prim 算法伪代码
变量含义解释：
S：生成树顶点集合，初始只含起点 v0。
mst[i]：存放 S 中距离顶点 i 最近的顶点编号。
lowcost[i]：存放 S 到顶点 i 的最短距离。
算法过程：
- 初始化顶点集合 S，一开始只将起点 v0 加入到 S 中。
- 初始化 mst 数组，初值均为 v0。
- 初始化 lowcost 数组，初值为 v0 到各顶点的距离，无边则为 INF。
- 重复以下步骤，直到所有顶点都在 S 中为止：
- 将 lowcost 值最小的顶点 v 加入到 S 中。
- 更新与顶点 v 相邻顶点的 mst 值。
- 更新与顶点 v 相邻顶点的 lowcost 值。
图解 Prim 算法过程
初始状态
S = {A}
S = {A, F}
更新顶点 E 的 mst 为 F，lowcost 为 6
S = {A, F, B}
更新顶点 E 的 mst 为 B，lowcost 为 4
更新顶点 C 的 mst 为 B，lowcost 为 8
S = {A, F, B, E}
更新顶点 C 的 mst 为 E，lowcost 为 7
更新顶点 D 的 mst 为 D，lowcost 为 9
S = {A, F, B, E, C}
更新顶点 D 的 mst 为 C，lowcost 为 3
S = {A, F, B, E, C, D}
至此，我们就找到了最小生成树。
Prim 算法 C++ 源代码
在下面的代码中，我们通过将顶点的 lowcost 设为 0 来表示将顶点加入到集合 S 中，并将该顶点输出到命令行。
// -----------------------------------------------------
// Copyright (c) 2017, Wray Zheng. All Rights Reserved.
// Distributed under the BSD License.
// -----------------------------------------------------
#include <iostream>
#include <cstdio>
#define INF 10000
using namespace std;
typedef char DATATYPE;
/* 功能：创建图的邻接矩阵
* 参数：顶点序列、边序列、用于存放顶点个数和顶点数据的变量
* 返回值：邻接矩阵（二级指针）
*/
int** CreateMGraph(char* vertex, char* edges, int& vNum, DATATYPE*& vData) {
char index[128]; //存放顶点字符对应的下标
char* p = vertex;
int count = 0;
//计算顶点个数
while (*p++ != '\0') count++;
vNum = count;
//初始化顶点数组
vData = new DATATYPE[count+1];
for (int i = 0; i < count; i++) {
vData[i] = vertex[i];
}
vData[count] = '\0';
//初始化顶点下标数组
for (int i = 0; i < count; i++) {
index[vertex[i]] = i;
}
//初始化邻接矩阵
int** MGraph = new int*[count];
for (int i = 0; i < count; i++) {
MGraph[i] = new int[count];
for (int j = 0; j < count; j++) {
MGraph[i][j] = INF;
}
}
//将权值传入顶点矩阵
char* pEdge = edges;
char u, v;
int weight;
int flag;
while(true) {
flag = sscanf(pEdge, "(%c,%c,%d)", &u, &v, &weight);
//边序列读取完毕
if(flag != 3) break;
MGraph[index[u]][index[v]] = weight;
MGraph[index[v]][index[u]] = weight;
//找到下一条边的读取位置
while (*pEdge++ != ')');
}
return MGraph;
}
/* 功能：求最小生成树
* 参数：邻接矩阵、顶点数据、顶点个数
*/
void Prim(int** MGraph, DATATYPE* vData, int vNum) {
int* lowcost = new int[vNum];
int* mst = new int[vNum];
//初始化lowcost与mst数组
for (int i = 0; i < vNum; i++) {
lowcost[i] = MGraph[0][i];
mst[i] = 0;
}
//寻找最小生成树
int min;
int minid;
int totalWeight = 0;
for(int i = 0; i < vNum - 1; i++) {
//查找与顶点集S连接的代价最小的边
min = INF;
minid = -1;
for (int j = 1; j < vNum; j++) {
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
minid = j;
}
}
//将找到的顶点加入到顶点集S中（此处为输出），并将代价设为0
cout << vData[mst[minid]] << "-" << vData[minid] << " = " << min << endl;
totalWeight += min;
lowcost[minid] = 0;
//更新lowcost与mst
for (int j = 1; j < vNum; j++) {
if (MGraph[minid][j] < lowcost[j]) {
lowcost[j] = MGraph[minid][j];
mst[j] = minid;
}
}
}
cout << "Total Weight: " << totalWeight << endl;
}
int main() {
int** MGraph;
int vNum = 0;
DATATYPE* vData;
char vertex[] = "ABCDEF";
char edges[] = "(A,B,5)(A,F,2)(B,C,8)(B,E,4)(C,D,3)(C,E,7)(D,E,9)(E,F,6)";
MGraph = CreateMGraph(vertex, edges, vNum, vData);
Prim(MGraph, vData, vNum);
return 0;
}
作者：Wray Zheng
原文：http://www.codebelief.com/article/2017/04/prim-algorithm-introduction/
