[算法与数据结构] - No.9 图论（2）- 最小生成树Prim算法与Kruskal算法

本文主要是介绍[算法与数据结构] - No.9 图论（2）- 最小生成树Prim算法与Kruskal算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

普里姆算法的基本思想：
从连通网络 N = { V, E }中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。

如图所示：

算法实现：

设初始总的顶点集合为V，已加入最小生成树的集合点为S

定义两个辅助数组：lowcost[] 和 nextvex[],分别用来记录下标为i的到S中点最近的距离。每一次选取不在S中，同时距离S最近的点vi。将vi加入S中，同时在lowcost

中更新所有不在S中的, 与vi相连的点vj到S的最近距离。更新nextvex中vj下标的值为vi,即nextvex[vj] = vi

#include <iostream>
#include <stdlib.h>
using namespace std;
const int MAX =99999999;
int main()
{unsigned int n,e;cin>>n>>e;if(n>0&&e>0){int arr[100][100];int nextvex[100] = {0};nextvex[0] = -1;int lowcost[100] = {0};for(int i=0; i<100; i++){for(int j=0; j<100; j++){if(i!=j)arr[i][j] = MAX;elsearr[i][j] = 0;}}for(int i=0; i<e; i++){int from,to,dis;cin>>from>>to>>dis;arr[from][to] = dis;arr[to][from] = dis;//arr[to][from] = dis;}for(int j =0;j<n;j++){lowcost[j] = arr[0][j];}/*for(int i=0; i<n; i++){for(int j=0; j<n; j++){cout<<arr[i][j]<<" ";}cout<<endl<<endl;}*/int cnt = 1;while(cnt<n){int temp = MAX;int vertex;for(int k = 0;k<n;k++){if(nextvex[k]!=-1&&lowcost[k]<temp){temp = lowcost[k];vertex = k;}}cout<<nextvex[vertex]<<"->"<<vertex<<":"<<temp<<endl;nextvex[vertex] = -1;for(int l = 0;l<n;l++){if(arr[vertex][l]<MAX&&nextvex[l]!=-1){lowcost[l] = arr[vertex][l];nextvex[l] = vertex;}}cnt = cnt + 1;}}return 0;
/*
7 9
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24*/
}

Kruskal算法基本思想：

j将所有的边排序。将所有的边加入集合S，即一开始S = E 。从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E' 。重复直到所有点属于同一棵树，边集E'就是一棵最小生成树

这个算法的思想很简单，但是其中有个地方值得注意。那就是如何判断两个点是否处于同一个连通分量（同一棵树里），这里用到了并查集：

并查集：当我们需要判断某两个元素是否属于统一集合（这里是树），在数据量比较大的时候，我们用到了并查集。并查集中有两个重要的函数（初始化函数除外），按秩合并和路径压缩

初始化：

typedef struct Edge{int from;int to;int cost;
}Edge;
Edge edgeList[100];int nodeRank[100];
int nodeFather[100];
void Init(int n)
{for(int i = 0 ;i<n;i++){nodeRank[i] = 0;nodeFather[i] = i;}
}

首先，我们定义一个边的结构体。这个结构体里面定义了每个边的两个端点。同时记录这条边的长度。在初始化的函数中，我们设置每个节点的父节点是自身，同时每个节点的秩都是0。

路径压缩：

int findFather(int x)
{int root = x;while(nodeFather[root]!=root){root = nodeFather[root];}while(x!=root){int father = nodeFather[x];nodeFather[x] = root;x = father;}return root;
}

在我们查找两个节点是否处于同一个树的时候，我们的方法是不断找当前节点的父节点，查看其父节点是否为自身。如果是，该节点为该树的根；否则迭代该过程。但是，随着树的增加，每次查找父节点会很消耗时间。所以我们每次查找父节点的时候，都将除根节点以外所有节点的父节点设为根节点，方便下次查找。

按秩合并：

int unite(int x,int y)
{int fatherx = findFather(x);int fathery = findFather(y);if(nodeRank[fatherx]>nodeRank[fathery]){nodeFather[fathery] = fatherx;}else{nodeFather[fatherx] = fathery;if(nodeRank[fatherx] == nodeRank[fathery]){nodeRank[fathery]++;}}
}

如果两个子节点不在同一树里边，那么我们设置秩（我们这里是根节点的索引大小）较小的根指向秩比较大的根。

当最小生成树中的边的个数达到n-1的时候，算法结束

完整代码如下：

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Edge{int from;int to;int cost;
}Edge;
Edge edgeList[100];
int cmp(const void*first,const void*second)
{return ((Edge*)first)->cost - ((Edge*)second)->cost;
}
int nodeRank[100];
int nodeFather[100];
void Init(int n)
{for(int i = 0 ;i<n;i++){nodeRank[i] = 0;nodeFather[i] = i;}
}
int findFather(int x)
{int root = x;while(nodeFather[root]!=root){root = nodeFather[root];}while(x!=root){int father = nodeFather[x];nodeFather[x] = root;x = father;}return root;
}int unite(int x,int y)
{int fatherx = findFather(x);int fathery = findFather(y);if(nodeRank[fatherx]>nodeRank[fathery]){nodeFather[fathery] = fatherx;}else{nodeFather[fatherx] = fathery;if(nodeRank[fatherx] == nodeRank[fathery]){nodeRank[fathery]++;}}
}void Kruskal(int n,int e)
{int cnt = 0;qsort(edgeList,e,sizeof(Edge),cmp);/*for(int i = 0 ; i <e;i++){cout<<edgeList[i].from<<" "<<edgeList[i].to<<" "<<edgeList[i].cost<<endl;}*/for(int i = 0 ; i<e&&cnt!=n-1;i++){if(findFather(edgeList[i].from)!=findFather(edgeList[i].to)){cout<<edgeList[i].from<<" "<<edgeList[i].to<<endl;unite(edgeList[i].from,edgeList[i].to);cnt++;}}
}
/*
//一种优美的递归形式
int find(int x)
{if(x!=father[x]){father[x] = find(father[x]);}return father[x];
}
*/
int main()
{cout<<"请输入顶点数和边数："<<endl;int n,e;cin>>n>>e;for(int i = 0 ; i <e;i++){cin>>edgeList[i].from>>edgeList[i].to>>edgeList[i].cost;}Init(n);Kruskal(n,e);return 0;/*
7 9
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24*/
}