普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。我们之前介绍的Kruskal算法适用于稀疏图(一般我们认为满足|E| < V*(V-1)/4时，图为稀疏图， |E|为边的数量，V为顶点数)。我们将要介绍的Prim算法则是适用于稠密图(我们这里所说的适用于某种情况，只表示该算法在这个条件下效率最优)。
1、算法描述
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
[cpp] view plain copy print ? 输入：一个加权连通图，其中顶点集合为V，边集合为E 输出：使用集合Vnew和Enew来描述所得到的最小生成树 算法流程： 1.初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}； 2.重复下列操作，直到Vnew = V: <1>在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； <2>将v加入集合Vnew中，将（u, v）加入集合Enew中； 输入：一个加权连通图，其中顶点集合为V，边集合为E 输出：使用集合Vnew和Enew来描述所得到的最小生成树 算法流程： 1.初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}； 2.重复下列操作，直到Vnew = V: <1>在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； <2>将v加入集合Vnew中，将（u, v）加入集合Enew中；下面给出一个无向图，每条边上的数字为权值：
我们任选一个顶点作为起始点，这里我们随便选一个，就以D作为起始点。现在集合Vnew = { D }， Enew = { }。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示(下同)。因为顶点A是距离集合Vnew最近的点，所以我们将A加入集合，所以现在集合为 Vnew = { A， D}， Enew = { (A, D) }。
下一个顶点为距离集合Vnew最近的顶点(也就是距离D或A最近的点)。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，所以我们将顶点F加入集合Vnew，将边(D, F)加入集合 Enew。现在集合变为 Vnew = { A， D, F }, Enew = { (A, D) , (D, F) }。
我们继续重复上面的步骤。我们可以发现距离集合Vnew最近的点为B，(A, B)距离为 7 。所一我们将B加入集合Vnew， 将边(A, B)加入集合Enew。现在集合就变为 Vnew = { A, B, D, F }, Enew = { (A, B), (A, D), (D, F) }。
我们只要不断的重复上述步骤，很快我们就找到了该图的最小生成树(如图所示)
有兴趣的朋友，还可以试试用其他顶点作为起点看看答案是否一致。最后你会惊奇的发现无论你取哪一个点，最后的答案都是一致的。
2、Prim算法的时间复杂度
Prim算法循环|V| - 1，每次都要寻找距离集合Vnew的最小值， 扫描与一个点所连接的所有边。如果使用将一个点所有的边都扫描一遍的算法，则时间复杂度为O(|V|² + |E|)。如果我们使用二叉堆来实现查找距离集合Vnew的最小值，则时间复杂度为O(|E| log |V| )。如果使用斐波那契堆优化的话，那么时间复杂度将可以近一步优化为O(|E| + |V | log|V|)。
3*、Prim算法的证明（不感兴趣的可以直接跳过）
[cpp] view plain copy print ? 设Prim生成的树为G0 假设存在Gmin使得cost(Gmin)<cost(G0) 则在Gmin中存在(u,v)不属于G0 将(u,v)加入G0中可得一个环，且(u,v)是该环的最长边 这与prim每次生成最短边矛盾 故假设不成立，得证. 设Prim生成的树为G0 假设存在Gmin使得cost(Gmin)<cost(G0) 则在Gmin中存在(u,v)不属于G0 将(u,v)加入G0中可得一个环，且(u,v)是该环的最长边 这与prim每次生成最短边矛盾 故假设不成立，得证.4、Prim算法的实现
这里我们就用一到题目来说明Prim算法的实现 还是畅通工程 。大家可以先思考思考，看看能不能根据上面的描述自己实现Prim算法，下面附上这一题的代码，以供参考：
【未优化版】
[cpp] view plain copy print ? #include <cstdio> #include <vector> #define INF 0xfffffff #define MAXN 100 + 10 using namespace std; struct Vex{ int v, weight; Vex(int tv, int tw):v(tv), weight(tw){} }; vector<Vex> graph[MAXN]; bool inTree[MAXN]; int mindist[MAXN]; void Init(int n){ for(int i = 1; i <= n; i++){ mindist[i] = INF; inTree[i] = false; graph[i].clear(); } } int Prim(int s, int n){ int addNode, tempMin, tempVex ,ret = 0; //将顶点S加入集合Vnew inTree[s] = true; //初始化，各点到集合Vnew的距离， 数组mindist表示各点到集合Vnew的最小距离 for(unsigned int i = 0; i < graph[s].size(); i++) mindist[graph[s][i].v] = graph[s][i].weight; //因为还有n-1个点没有加入集合Vnew，所以还要进行n-1次操作 for(int NodeCount = 1; NodeCount <= n-1; NodeCount++){ tempMin = INF; //在还没有加入集合Vnew的点中查找距离集合Vnew最小的点 for(int i = 1; i <= n; i++){ if(!inTree[i] && mindist[i] < tempMin){ tempMin = mindist[i]; addNode = i; } } //将距离集合Vnew距离最小的点加入集合Vnew inTree[addNode] = true; //将新加入边的权值计入ret ret += tempMin; //更新还没有加入集合Vnew的点 到 集合Vnew的距离 for(unsigned int i = 0; i < graph[addNode].size(); i++){ tempVex = graph[addNode][i].v; if(!inTree[tempVex] && graph[addNode][i].weight < mindist[tempVex]){ mindist[tempVex] = graph[addNode][i].weight; } } } return ret; } int main(){ int n; int v1, v2, weight; while(scanf(“%d”, &n), n){ Init(n); for(int i = 0; i < n*(n-1)/2; i++){ scanf(”%d%d%d”, &v1, &v2, &weight); graph[v1].push_back(Vex(v2, weight)); graph[v2].push_back(Vex(v1, weight)); } printf(”%d\n”, Prim(1, n)); } return 0; } #include <cstdio> #include <vector> #define INF 0xfffffff #define MAXN 100 + 10 using namespace std; struct Vex{ int v, weight; Vex(int tv, int tw):v(tv), weight(tw){} }; vector<Vex> graph[MAXN]; bool inTree[MAXN]; int mindist[MAXN]; void Init(int n){ for(int i = 1; i <= n; i++){ mindist[i] = INF; inTree[i] = false; graph[i].clear(); } } int Prim(int s, int n){ int addNode, tempMin, tempVex ,ret = 0; //将顶点S加入集合Vnew inTree[s] = true; //初始化，各点到集合Vnew的距离， 数组mindist表示各点到集合Vnew的最小距离 for(unsigned int i = 0; i < graph[s].size(); i++) mindist[graph[s][i].v] = graph[s][i].weight; //因为还有n-1个点没有加入集合Vnew，所以还要进行n-1次操作 for(int NodeCount = 1; NodeCount <= n-1; NodeCount++){ tempMin = INF; //在还没有加入集合Vnew的点中查找距离集合Vnew最小的点 for(int i = 1; i <= n; i++){ if(!inTree[i] && mindist[i] < tempMin){ tempMin = mindist[i]; addNode = i; } } //将距离集合Vnew距离最小的点加入集合Vnew inTree[addNode] = true; //将新加入边的权值计入ret ret += tempMin; //更新还没有加入集合Vnew的点 到 集合Vnew的距离 for(unsigned int i = 0; i < graph[addNode].size(); i++){ tempVex = graph[addNode][i].v; if(!inTree[tempVex] && graph[addNode][i].weight < mindist[tempVex]){ mindist[tempVex] = graph[addNode][i].weight; } } } return ret; } int main(){ int n; int v1, v2, weight; while(scanf("%d", &n), n){ Init(n); for(int i = 0; i < n*(n-1)/2; i++){ scanf("%d%d%d", &v1, &v2, &weight); graph[v1].push_back(Vex(v2, weight)); graph[v2].push_back(Vex(v1, weight)); } printf("%d\n", Prim(1, n)); } return 0; }【堆优化版】
[cpp] view plain copy print ? #include <cstdio> #include <vector> #include <queue> #define INF 0xfffffff #define MAXN 100 + 10 using namespace std; struct Vex{ int v, weight; Vex(int tv = 0, int tw = 0):v(tv), weight(tw){} bool operator < (const Vex& t) const{ return this->weight > t.weight; } }; vector<Vex> graph[MAXN]; bool inTree[MAXN]; int mindist[MAXN]; void Init(int n){ for(int i = 1; i <= n; i++){ mindist[i] = INF; inTree[i] = false; graph[i].clear(); } } int Prim(int s, int n){ priority_queue<Vex> Q; Vex temp; //res用来记录最小生成树的权值之和 int res = 0; //将s加入集合Vnew，并更新与点s相连接的各点到集合Vnew的距离 inTree[s] = true; for(unsigned int i = 0; i < graph[s].size(); i++){ int v = graph[s][i].v; if(graph[s][i].weight < mindist[v]){ mindist[v] = graph[s][i].weight; //更新之后，加入堆中 Q.push(Vex(v, mindist[v])); } } while(!Q.empty()){ //取出到集合Vnew距离最小的点 temp = Q.top(); Q.pop(); int addNode = temp.v; if(inTree[addNode]) continue; inTree[addNode] = true; res += mindist[addNode]; //更新到集合Vnew的距离 for(unsigned int i = 0; i < graph[addNode].size(); i++){ int tempVex = graph[addNode][i].v; if(!inTree[tempVex] && mindist[tempVex] > graph[addNode][i].weight){ mindist[tempVex] = graph[addNode][i].weight; Q.push(Vex(tempVex, mindist[tempVex])); } } } return res; } int main(){ int n; int v1, v2, weight; while(scanf(“%d”, &n), n){ Init(n); for(int i = 0; i < n*(n-1)/2; i++){ scanf(”%d%d%d”, &v1, &v2, &weight); graph[v1].push_back(Vex(v2, weight)); graph[v2].push_back(Vex(v1, weight)); } printf(”%d\n”, Prim(1, n)); } return 0; } #include <cstdio> #include <vector> #include <queue> #define INF 0xfffffff #define MAXN 100 + 10 using namespace std; struct Vex{ int v, weight; Vex(int tv = 0, int tw = 0):v(tv), weight(tw){} bool operator < (const Vex& t) const{ return this->weight > t.weight; } }; vector<Vex> graph[MAXN]; bool inTree[MAXN]; int mindist[MAXN]; void Init(int n){ for(int i = 1; i <= n; i++){ mindist[i] = INF; inTree[i] = false; graph[i].clear(); } } int Prim(int s, int n){ priority_queue<Vex> Q; Vex temp; //res用来记录最小生成树的权值之和 int res = 0; //将s加入集合Vnew，并更新与点s相连接的各点到集合Vnew的距离 inTree[s] = true; for(unsigned int i = 0; i < graph[s].size(); i++){ int v = graph[s][i].v; if(graph[s][i].weight < mindist[v]){ mindist[v] = graph[s][i].weight; //更新之后，加入堆中 Q.push(Vex(v, mindist[v])); } } while(!Q.empty()){ //取出到集合Vnew距离最小的点 temp = Q.top(); Q.pop(); int addNode = temp.v; if(inTree[addNode]) continue; inTree[addNode] = true; res += mindist[addNode]; //更新到集合Vnew的距离 for(unsigned int i = 0; i < graph[addNode].size(); i++){ int tempVex = graph[addNode][i].v; if(!inTree[tempVex] && mindist[tempVex] > graph[addNode][i].weight){ mindist[tempVex] = graph[addNode][i].weight; Q.push(Vex(tempVex, mindist[tempVex])); } } } return res; } int main(){ int n; int v1, v2, weight; while(scanf(“%d”, &n), n){ Init(n); for(int i = 0; i < n*(n-1)/2; i++){ scanf(“%d%d%d”, &v1, &v2, &weight); graph[v1].push_back(Vex(v2, weight)); graph[v2].push_back(Vex(v1, weight)); } printf(“%d\n”, Prim(1, n)); } return 0; }如果不了解priority_queue的朋友可以参考：Here。
【斐波那契堆优化】
先挖个坑，以后再填，有兴趣的朋友可以自行完善。
想找一些题练练手朋友，可以移步到这里：图论五百题
