克鲁斯卡尔算法
一、最小生成树简介
假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
图的生成树是它的一颗含有其所有顶点的无环连通子图，一幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和)最小的生成树。下图为一幅加权无向图和它的最小生成树.(箭头不指示方向,标红的为最小生成树)：
最小生成树可以使用克鲁斯卡尔算法和普里姆算法实现。
二、克鲁斯卡尔算法
1、算法思路
1. 将图中的所有边都去掉；
2. 将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环 ；
3. 重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
2、图解克鲁斯卡尔算法
【Note】：
（1）如何判断环：使用一个multiset存储所有边的信息，如果起点和终点都在st1中则加入该边会形成环。
3、克鲁斯卡尔算法的demo：
#include <bits/stdc++.h>
using namespace std;
struct edge//纪录边的信息
{
int start;
int end;
int weight;
};
//克鲁斯卡尔算法
void Kruskal(int data[10][3])
{
int data2[10][2] = {0};
multiset<int> st1;
vector<edge> vec;//存储所有边的信息
edge temp;
for (int j = 0; j < 10; ++j)//初始化所有边的信息
{
temp.start = data[j][0];
temp.end = data[j][1];
temp.weight = data[j][2];
vec.push_back(temp);
}
//按权值排序
sort(vec.begin(), vec.end(), [](const edge &e1, const edge &e2) -> bool
{
return e1.weight < e2.weight ? true : false ;
});
for (int j = 0; j < 10; ++j)
{
//st1存放的是已经加入的边用于判断是否会形成环（如果起点和终点都在st1中则加入该边会形成环）
if (st1.find(vec[j].start) != st1.end() && st1.find(vec[j].end) != st1.end())
continue;
else
{
data2[j][0] = vec[j].start;//data2存放的是组成最小生成树的边
data2[j][1] = vec[j].end;
st1.insert(vec[j].start);
st1.insert(vec[j].end);
}
}
for (int j = 0; j < 10; ++j)
{
if (data2[j][0] != 0)
cout << data2[j][0] << " " << data2[j][1] << endl;
}
}
int main(int argc, char const *argv[])
{
int data[10][3] = //所有边的信息
{
{1,2,6},{1,6,12},
{1,5,10},{2,3,3},
{2,4,5},{2,6,8},
{3,4,7},{4,6,11},
{4,5,9},{5,6,16}
};
Kruskal(data);
return 0;
}三、普里姆算法
1、算法思路
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。 从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
2、图解普里姆算法
【Note】：
（1）复杂度分析：克鲁斯卡尔算法的时间复杂度为O(eloge)；普里姆算法的时间复杂度为，邻接矩阵：O(v^2)，邻接表：O(elog2v)。
（2）克鲁斯卡尔算法主要针对边展开，边数少时效率会很高，所以对于稀疏图有优势而普利姆算法对于稠密图，即边数非常多的情况会好些。