最小生成树的实现：prim算法&&kruskal算法
最小生成树的概念：
首先我们来看生成树的概念：
这是一个相对于有N个顶点的图的概念，说白了就是从一个顶点出发，经过N-1条边能够实现所有顶点的连通（遍历N个顶点），因为得到的结构与树相同（N个顶点N-1条边），故称为图的生成树。我认为生成树和图的最大区别就在于生成树不会有回路，例：
由第一个图可以生成这些生成树，显然，一个图中可以有多个生成树，并且从不同的顶点出发，可以得到不同的生成树。当然，这是相对于连通图来说，否则也无法遍历到所有顶点。
而最小生成树就是在符合生成树的基础上，得到所有生成树中边权之和最小的，就是最小生成树，我理解为成本最低的并能使图连通的方案。
下面就来看看得到最小生成树的两种算法。
prim算法：
其实和dijkstra算法很相似，区别以及注意事项：
（1）prim算法中dist不再是顶点到源点的最短距离，而是顶点到收录顶点的集合S的最短距离，因此，收录进S中的顶点的dist值就是0了，所以我们不需要用额外的visited来判断顶点是否被收录，而是看看dist是否为0。
（2）并且我们用并查集（也就是子节点值为父节点的数组）来存放得到的生成树。
（3）核心在于我们每次都收录离集合S最近的顶点（边权最小）来实现最小的要求（贪心算法）。
（4）并在最后判断是否遍历了所有顶点，如果没有，那么说明图G是不连通的。
#include <iostream>
#define maxn 1000
#define INF 1000000000
using namespace std;
int G[maxn][maxn];//邻接矩阵表示图，对于不存在的边初始化为INF（最大值）
int dist[maxn];//dist在这里表示某顶点到已经收录进S的整个集合的距离 ,所以我们完全可以用dist兼顾visited的作用
int parent[maxn];//用并查集存最小生成树
int sum=0;//存最小生成树的权重
int countV=0;//存最小生成树的顶点数
int FindMindistV(int N)
{
int MinV,V;
int mindist=INF;
for(V=0;V<N;V++){
if(dist[V]!=0&&dist[V]<mindist){//注意条件相对于dijkstra发生的变化！！！
mindist=dist[V];
MinV=V;
}
}
if(mindist<INF){
return MinV;
}else{
return -1;
}
}
void Prim(int s,int N)//从顶点s开始找最小生成树
{
for(int i=0;i<N;i++){
dist[i]=G[s][i];
parent[i]=s;//初始化所有顶点的父节点都是s
}
//放入顶点s
parent[s]=-1;
dist[s]=0;
countV++;
// 开始遍历
while(1){
int v=FindMindistV(N);//注意第一次循环时这个v不再是s！！！
if(v==-1) break;
countV++;
sum+=dist[v];
dist[v]=0;
//继续下一层收入
for(int w=0;w<N;w++){
if(dist[w]!=0&&G[v][w]<INF){//
if(dist[w]>G[v][w]){//如果w到集合S的距离大于 w到集合S中顶点v的距离
dist[w]=G[v][w]; //更新w到集合S的距离
parent[w]=v; //更新树
}
}
}
}
if(countV<N){//说明图不连通，并没有遍历到所有顶点
sum=-1;
}
return;
}
int main()
{
//根据需求输入输出初始化
}
因为我们还是遍历了所有顶点以及找他们的邻接点，所以时间复杂度为O（N2），对于稠密图来说还可以接受，简单粗暴，而对于稀疏图就不大合适了，所以我们有另外一种，也就是下面这个算法。
kruskal算法：
如果图很稀疏，比如边数很接近顶点数，那么我们想得到的边数本就是顶点数-1，这时再去用prim算法遍历所有顶点就很不合算了，所以我们用另外一种思想——将森林合并成树：其实就是在初始情况下，认为每一个顶点都是一棵树，我们通过每次把最小的边收进来来实现两棵树的合并，最后把所有顶点都并成一棵树，关键在于，每次合并都要注意不能让合并后的结构中存在回路！！！
我们先来看伪代码：（MST是用来存边的集合）
那么问题来了，该怎样判断合并后的结构中是否存在回路呢？，其实就是判断加入进来的边的两个顶点是否在同一棵树中，显然，如果他们在同一棵树中且他们不是树的根节点那么一定会构成回路，并查集恰好能便于查找根节点，只要通过并查集找到两个顶点所在树的根节点，看是否相同即可，如果相同就舍弃，不同就合并。
其次，我们来看时间复杂度，显然我们要在找最小边的时候做文章，如果我们遍历所有的边来找，那么也将到达平方的数量级，和第一种没区别，但是这里我们可以用最小堆（优先队列）来存所有的边，然后每次弹出根节点。这样时间复杂度只有O（ElogE），而在用并查集查根节点和合并时的时间复杂度时O（VlogV），所以总体时间复杂度为O（VlogV）。对于稀疏图比较友好。
下面来看具体实现的代码：
#include <iostream>
#include <vector>
#include <queue>
#define maxn 1000
#define INF 1000000000
using namespace std;
struct node{
int v;
int weight;
};
struct Node{//存边用的
int v1,v2;
int weight;
friend bool operator < (Node E1,Node E2){//让权值小的边优先级大
return E1.weight > E2.weight;
}
};
vector<node> G[maxn];//邻接表表示图，只是因为省时间，不过这里用不到。。。。。。
int sum=0;//存最小生成树的权重和
int countE=0;//存最小生成树的边数
int S[maxn];//用并查集存最小生成树
priority_queue<Node> q;//优先队列代替最小堆存边权
void InitializeVSet(int N)
{ /* 初始化并查集 */
int X;
for(X=0;X<N;X++)
S[X]=-1;
}
int FindRoot(int X)//查找X的根节点并压缩路径
{
if(S[X]<0){
return X;
}else{
return S[X]=FindRoot(S[X]);
}
}
void Union(int Root1,int Root2)//合并两课树
{
if(S[Root1]<S[Root2]){
S[Root2]=Root1;
S[Root1]+=S[Root2];
}else{
S[Root1]=Root2;
S[Root2]+=S[Root1];
}
}
bool CheckCycle(int V1,int V2)
{ /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
int Root1, Root2;
Root1 = FindRoot( V1 ); /* 得到V1所属的连通集名称 */
Root2 = FindRoot( V2 ); /* 得到V2所属的连通集名称 */
if( Root1==Root2 ) /* 若V1和V2已经连通，则该边不能要 */
return false;
else { /* 否则该边可以被收集，同时将V1和V2并入同一连通集 */
Union( Root1, Root2 );
return true;
}
}
void Kruskal(int N)
{
Node E;
InitializeVSet(N); /* 初始化顶点并查集 */
while (countE<N-1) { /* 当收集的边不足以构成树时 */
if (q.empty()) /*一定要先判断是否为空，否则q.top()可能出错*/
break;
E = q.top(); /* 从边集中得到最小边 */
q.pop();
/* 如果该边的加入不构成回路，即两端结点不属于同一连通集 */
if ( CheckCycle(E.v1,E.v2)==true ) {
sum += E.weight; /*累计权重 */
countE++; /* 生成树中边数加1 */
}
}
if ( countE < N-1 )//图不连通
sum = -1;
}
int main()
{
//根据需求输入输出初始化
}
细节都在注释中给出，仔细体会。