生成最小树（普里姆算法与库鲁斯卡尔算法）

普里姆算法

基本思想：以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小树。

代码如下：

vector<vector<int>> edges;//邻接矩阵 int N;//N为顶点数 //普里姆算法，从编号为0顶点开始 void prim() { vector<int> index(N, 0);//储存对应顶点的下标，初始化为第一个顶点的下标0 vector<int> lowcost(edges[0]);//表示已加入生成树的顶点到其他顶点之间权值的最小值，如果为INT_MAX表示它们之间没有边 lowcost[0] = 0;//lowcost[i] = 0, 表示编号为i的顶点已加入生成树，这里把第一个顶点加入生成树 for (int i = 1; i < N; ++i)//找到N-1条边 { //找到没有加入到生成树中且最小的权值的顶点下标cur int Min = INT_MAX, cur = 0; for (int j = 1; j < N; ++j) { if (lowcost[j] != 0 && lowcost[j] < Min) {/*lowcost[j]!=0表示没有加入到生成树*/ Min = lowcost[j]; cur = j; } } cout<<"("<<index[cur]<<","<<cur<<")"<<endl;//这就是生成树其中的一条边，将它输出 lowcost[cur] = 0;//表示将编号为cur的顶点加入生成树 //更新lowcast for (int j = 1; j < N; ++j) {/*将当前顶点与其他没被加入顶点之间的权值与lowcost中对应的权值比较，若小于加入待用*/ if (lowcost[j] != 0 && edges[cur][j] < lowcost[j]) { lowcost[j] = edges[cur][j]; index[j] = cur;//储存下标 } } } }

下面以一个例子来介绍算法该算法流程： 第一次循环：此时v0已加入最小树，lowcost储存着(v0, v1), (v0, v5)的权值，找到(v0, v1)的的权值最小，将v1加入生成树，(v0, v1)即是生成树的一条边。然后更新lowcost，将v1与其他没被加入生成树顶点之间权值拿来比较，加入lowcost备用，此时lowcost储存着(vo, v5), (v1, v2), (v1, v8), (v1, v6)的权值。 第二次循环：遍历找到(v0, v5)的权值最小，把v5加入最小树，得到生成树的一条边(v0, v5),然后继续更新lowcost，把v5与其他没被加入生成树顶点之间权值拿来比较，加入lowcost备用，此时lowcost储存(v1, v2), (v1, v8), (v1, v6), (v5, v6), (v5, v4)的权值。 如此反复，经过不断地转换与构造最终得到生成树所有的边。

克鲁斯卡尔算法

算法思想：通普里姆算法一样的思路，只不过是直接以边为目标去构建，直接去找最小权值的边来构造最小生成树，但要考虑是否会构成回路。 这里要用到图的储存结构中边集数组结构

struct edge { int Begin; int weight; int End; edge(int b = 0, int w = 0, int e = 0):Begin(b), weight(w), End(e){} bool operator < (edge& e) { return weight < e.weight; } };

这里不再赘述。 代码如下

struct edge { int Begin; int weight; int End; edge(int b = 0, int w = 0, int e = 0):Begin(b), weight(w), End(e){} bool operator < (edge& e) { return weight < e.weight; } }; int N, E;//顶点数和边数。 int Find(vector<int>& p, int f)//查找集合中从f开始的终点 { while (p[f] > 0) f = p[f]; return f; } void kruskal(vector<edge>& a) { sort(a.begin(), a.end());//按权值从小到大排序 vector<int> parent(N, 0);//用来判断是否构成回路，其详细作用后面会讲到 for (int i = 0; i < E; ++i) { int m = Find(parent, a[i].Begin); int n = Find(parent, a[i].End); if (m != n)//如果m==n表示a[i]边的两个顶点在同一个生成树边集和里，如果相连就会构成回路 { cout<<a[i].Begin<<" "<<a[i].End<<endl;//得到了生成树的一条边 parent[m] = n;//将a[i]边尾顶点放到下标为起点的parent中 } } }

拿上述例子介绍该算法流程 排序后的数组a

边BeginEndweighta[0]477a[1]288a[2]0110a[3]0511a[4]1812a[5]3716a[6]1616a[7]5617…

1.i = 0时得到通过调用Find得到m = 4， n = 7，他们不相等所以为生成树的一条边。并使parent[4] = 7，表示4和7在同一个生成树集里。 2.i = 1时得到m = 2，n = 8，他们不相等所以为生成树的一条边。并使2,8在同一个生成树集里。 3.i =2,3,4,5,6时同理，这时得到parent为[1,5,8,7,7,8,0,0,6]这个数组表示了目前两个生成树边连通集A，B，parent[0] = 1表示v0，v1在A中，然后以1为下标parent[1] = 5表示v1，v5在连通集A中，parent[5] = 8表示v5，v8在A中，parent[8] = 6,表示v8，v6在A中，parent[6] = 0说明A已经到头，又可以发现parent[2]=8,所以v2，v8也在A中，此时边集A中有v0，v1，v5，v8，v6，v2。同理B中有v3，v4，v7。 4.i = 7时，得到m=n=6，所以表示a[7]边的顶点5,6再一个边集中，如果连接则会构成回路，因此跳过。

此后如此反复找到所有生成树的边。

二者之间的比较：

普里姆算法的时间复杂度为O(n^2),n为顶点数。其主要针对顶点展开，在边较多的稠密图时较好。 库鲁斯卡尔算法的时间复杂度为eloge，e为边数。其主要针对边展开，在边较少的稀疏图时效率很高。

例题：

7-10 公路村村通 (30分) 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式: 输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例: 6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3 输出样例: 12

解法一：普里姆算法

#include <bits/stdc++.h> using namespace std; vector<vector<int>> edges; int N, E, ans = 0; bool prim() { vector<int> index(N+1, 1); vector<int> lowcast(edges[1]); lowcast[1] = 0; for (int i = 1; i < N; ++i) { int Min = INT_MAX, cur = -1; for (int j = 2; j <= N; ++j) { if (lowcast[j] != 0 && lowcast[j] < Min) { Min = lowcast[j]; cur = j; } } if (cur == -1) return 0; ans += edges[index[cur]][cur]; lowcast[cur] = 0; //更新lowcast for (int j = 2; j <= N; ++j) { if (lowcast[j] != 0 && edges[cur][j] < lowcast[j]) { lowcast[j] = edges[cur][j]; index[j] = cur; } } } return 1; } int main() { cin>>N>>E; edges.resize(N+1); for (int i = 1; i <= N; ++i) { vector<int> tmp(N+1, INT_MAX); edges[i] = tmp; } for (int i = 1; i <= E; ++i) { int v1, v2, x; cin>>v1>>v2>>x; edges[v1][v2] = x; edges[v2][v1] = x; } cout<<(prim() == 1? ans:-1); return 0; }

解法二：库鲁斯卡尔算法

#include <bits/stdc++.h> using namespace std; struct edge { int Begin; int weight; int End; edge(int b = 0, int w = 0, int e = 0):Begin(b), weight(w), End(e){} bool operator < (edge& e) { return weight < e.weight; } }; int N, E, ans = 0, cnt = 0; int Find(vector<int>& p, int f) { while (p[f] > 0) f = p[f]; return f; } void kruskal(vector<edge>& a) { vector<int> parent(N+1, 0); for (int i = 1; i <= E; ++i) { int m = Find(parent, a[i].Begin); int n = Find(parent, a[i].End); if (m != n) { ans += a[i].weight; ++cnt; parent[m] = n; } } } int main() { cin>>N>>E; if (E < N - 1) { cout<<-1; return 0; } vector<edge> a(E+1); for (int i = 1; i <= E; ++i) { int v1, v2, x; cin>>v1>>v2>>x; a[i].Begin = v1; a[i].End = v2; a[i].weight = x; } sort(a.begin()+1, a.end()); kruskal(a); cout<<(cnt == N-1? ans:-1); return 0; }