背景：在学习图的知识时，最小生成树是一个最普遍的概念。它在日常生活中的应用很普遍，比如：有A、B、C、D、E五个城市，现在想在五个城市之间建设通信线路连通，每两个城市之间修建线路的费用不同，我们当然想用最小的代价将五个城市通信连接起来，这时，如何获取最小代价的方案，也就是如何找到最小生成树就显得尤为重要。
如何寻找最小生成树，目前常用的有Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法，接下来我们一个一个详细地介绍其原理。
为了方便理解，我们用一个图来直观地展示着两个算法。下图中A、B、C、D、E分别表示五个城市，每条边上的数字表示两个城市之间的修建通信线路的代价。设原图中顶点集合为U，关系集合为V；生成树中点的集合为u，关系集合为v。
Prim算法：
先选取一个顶点如A作为起点，将该点加入到集合u中，之后从和u中所有点相关联，且终点在集合U-u中的所有边中找出一条权值最小的边。将该边存入v中，同时将该边的终点存入到u。重复以上步骤直至u中包含U中所有点。图解如下所示。
下面我们再用文字来记录一下Prim算法寻找最小生成树的步骤：
选出顶点A，将A存入到集合u中。
此时u中只有顶点A，和A相关联且终点在U-u中的边有A->B，A->C，A->E，这三条边中权值最小的为A->B，将关系A->B加入到集合v，同时将点B加入到集合u。
此时u中有顶点A，B，和u中点相关联且终点在U-u中的边有A->C，A->E，B->C，这三条边中权值最小的为A->C，将关系->C加入到集合v，同时将点C加入到集合u。
重复以上步骤，直至u中包含所有点。
Prim算法的实现代码：
/**
* Prim算法代码实现，默认图中的第一个顶点序号为1
* @param graph 用于存储顶点到顶点之间的权值，例如graph[1][3]表示顶点1到顶点3之间的权值
* @param n 用于表示顶点的数量
*/
void Prim(int graph[][MAX], int n){
int mincost[MAX];//数组存储以i为顶点的边的最小权值
for (int k = 0; k < MAX; ++k) {
mincost[k] = MAXCOST;
}
int start[MAX];//数组存储以以i为顶点的最小权值的边的起点
for (int j = 0; j < MAX; ++j) {
start[j] = 1;
}
int min = MAXCOST, min_index = 1;//min用于表示权值最小边的权值，min_index用于表示该边的终点
//初始化,默认所有顶点的权值最小边是以第一个顶点为起点的
for (int i = 2; i <= n; ++i)
{
mincost[i] = graph[1][i];
}
//当mincost[i]=0时，表示将第i个顶点加入到到生成树中
mincost[1] = 0;
//每次寻找最小权值的边，将该边的终点加入到最小生成树中，循环n-1次，生成最小生成树
for (int i = 2; i <= n; ++i)
{
min = MAXCOST;
//for循环遍历mincost数组，找到权值最小的边
for (int i = 2; i <= n; ++i)
{
if (min > mincost[i] && mincost[i] != 0)
{
min = mincost[i];
min_index = i;
}
}
//将找到的最小边的终点加入到生成树中
mincost[min_index] = 0;
//更新mincost数组
for (int i = 2; i <= n; ++i)
{
if (graph[min_index][i] < mincost[i])
{
mincost[i] = graph[min_index][i];
start[i] = min_index;
}
}
}
//输出最小生成树
for (int i = 2; i <= n; ++i)
{
if (mincost[i] == 0)
{
cout<<start[i]<<"->"<<i<<"，权值为："<<graph[start[i]][i]<<endl;
}
}
}
/**
*测试用例
*/
int main() {
int graph[][6] = {
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, 2, 5, MAXCOST, 9,
MAXCOST, 2, MAXCOST, 7, MAXCOST, MAXCOST,
MAXCOST, 5, 7, MAXCOST, 6, 4,
MAXCOST, MAXCOST, 6, MAXCOST, 11,
MAXCOST, 9, MAXCOST, 4, 11, MAXCOST,
};
Prim(graph, 5);
return 0;
}
Kruskal算法：
每次从集合V中选出一条权值最小，且加入到v中后不会形成环的边，将该边从V中删除，并加入到v中，同时将该边的起点和终点加入到u中，若u中已有该顶点则忽略。重复上述步骤直至u中含有所有的点。图解如下所示：
下面我们用文字来记录一下Kruskal寻找最小生成树的步骤：
从集合V中选出一条权值最小且加入到v中后不会形成环的边，该边为A->B，将该边加入到v中，并从V中删除，同时将A，B两个点加入到u中。
从集合V 中再选出一条权值最小且加入到v中后不会形成环的边，该边为C->E，将该边加入到v中，并从V中删除，同时将C，E两个点加入到u中。
从集合V 中再选出一条权值最小且加入到v中后不会形成环的边，该边为A->C，将该边加入到v中，并从V中删除，同时将A，C两个点加入到u中。由于A，C已经在u中，忽略这两点。
从集合V 中再选出一条权值最小且加入到v中后不会形成环的边，该边为C->D，将该边加入到v中，并从V中删除，同时将C，D两个点加入到u中。由于C已经在u中，忽略C点。此时u中已经包含有所有的点，算法结束。
Kruskal实现代码：
/**
* Kruskal代码实现
* @param edges 存储图中的所有边的集合
* @param n 集合edges的元素个数
*/
void Kruskal(list<Edge*> edges){
//初始化并查集数据结构
DSU *dsu = new DSU();
//将集合中的边按照权值从小到大的顺序排序
edges.sort(EdgeSort);
//每次从集合中拿出一个权值最小边，如果起点和终点不在同一个连通图内，则将该边加入到最小生成树中
for (int i = 0; i < edges.size(); ++i) {
Edge *edge = edges.front();
int from = edge->start;
int end = edge->end;
if (dsu->merge(from, end)){
cout<<from<<"->"<<end<<"，权值为："<<edge->weight<<endl;
}
edges.pop_front();
}
}
/**
* 并查集实现
*/
DSU::DSU() {
for (int i = 0; i < 10; ++i) {
father[i] = i;
}
}
/**
* 将两个节点所在的连通子图合并
* @param x
* @param y
* @return 布尔值，true表示起点和终点不在同一个连通图内
*/
bool DSU::merge(int x, int y) {
int f1 = find(x);
int f2 = find(y);
//当x，y处于同一个连通图中的时候，合并失败
if (f1 == f2) {
return false;
}
father[f1] = f2;
return true;
}
/**
* 找到x的父节点
* @param x 参数节点
* @return 返回父亲节点
*/
int DSU::find(int x) {
if (x == father[x]){
return x;
}
return find(father[x]);
}
/**
*测试用例
*/
int main() {
Edge *edge1 = new Edge();
edge1->start = 1;
edge1->end = 2;
edge1->weight = 2;
Edge *edge2 = new Edge();
edge2->start = 1;
edge2->end = 3;
edge2->weight = 5;
Edge *edge3 = new Edge();
edge3->start = 1;
edge3->end = 5;
edge3->weight = 9;
Edge *edge4 = new Edge();
edge4->start = 2;
edge4->end = 3;
edge4->weight = 7;
Edge *edge5 = new Edge();
edge5->start = 3;
edge5->end = 4;
edge5->weight = 6;
Edge *edge6 = new Edge();
edge6->start = 3;
edge6->end = 5;
edge6->weight = 4;
Edge *edge7 = new Edge();
edge7->start = 4;
edge7->end = 5;
edge7->weight = 11;
list<Edge*> edges;
edges.push_back(edge1);
edges.push_back(edge2);
edges.push_back(edge3);
edges.push_back(edge4);
edges.push_back(edge5);
edges.push_back(edge6);
edges.push_back(edge7);
Kruskal(edges);
return 0;
}