Kruskal算法的思想如下
- 假设有n个顶点的连通图。首先先构造有顶点构成的集合0，每个顶点都是一个集合，不含有任何边。
- 在边找一个最小权值的边
- 判断这个边的俩个顶点是否来自于两个不同的集合，若是就将它俩归并为一个集合，然后将这个边添加到要构成的图的集合中。
-
直到上述的边的个数为顶点个数-1；否则，重复2-3；
算法构成树的过程如下：
如a图所示的图，下面是最小生成树的构造过程
image.png
（a）
image.png
(b)
image.png
(c)
image.png
(d)
image.png
(e)
image.png
(f)
image.png
在这里判断一个边的两个顶点是不是属于同一个集合，采用的是并查集的方式来实现
并查集的基本思想如下：
并查集可以用数组来和树来实现，在这里先讲树来实现。
1：树实现并查集：
属于同一个集合的结点拥有同一个根，图示如下：
image.png
上面的树中这些元素都属于一个集合，他们的根元素是1；
image.png
上面树中元素属于都属于一个集合，他们的根元素都是11；
两个集合合并就是将一个集合连在另一个集合的根元素的下面就好了。如下图所示：
image.png
那在合并集合的时候怎么合并集合呢？有没有想过，如下图所示的集合
image.png
一个树的高度很大，一个树的高度很小，这俩个集合在合并的时候要把高度小的集合合并在高度大的集合中。因为在合并集合中的元素的时候，首先要查找这个结点属于那个结点，若是将高度高的集合合并在高度小的集合中，就会增加查找的时间，增加程序的时间复杂度。
数组实现并查集
基本思想就是，在属于一个集合的数据都用一个数据来表示就好，在合并集合的时候，就将两个集合用一个数据来表示就好了，
如下图：
image.png
有0——7个数据；刚开始的时候他们都是一个集合，单独的个体，每个的根都是自己本身，-1表示他们都是单独个个体，是个根，在查找根结点的时候就是一个判断依据，只要对应的数据项是负数，那就说明这个是根；现在将1和2合并为一个集合如下图：
image.png
将1对应数据项和2对应的数据项合并在一起，放在1对应的数据项中，在这里面就是-1+-1；将2对应的数据项改为1，表示它的根现在是1；这就是一个集合。
现在将4，5归为一个集合如下图：
image.png
原理和上面的一样
现在讲3添加到2所集合中如下图：
image.png
首相查找2的根，发现是1，然后在查找3的根，发现是3，然后在1对应的数据项中加上3对应的数据项。也就是-2+-1；然后将3对应的数据项改为-1；
现在将5所在的集合和3所在的集合合并在一块如下图：
image.png
先查找5所在的根结点，发现是是4；现在在查找3所在的结点，发现是1；然后还是是和之前一样相加。将4对应的数据项和1对应的数据项相加，合并两个根就好，然后将4对应的数据项改为1；
现在6加到5所在的集合中如下图：
image.png
查找5所在的集合，5对应的数据项是4，4对应的数据项是1，1对应的数据项是负数，说明这个是根，然后还是相加，还是合并；就好了
</br>
好了，并查集讲完了接下来就是树了
算法的流程图如下：
未命名文件.jpg
程序如下：
#include <iostream>
using namespace std;
typedef struct node {
int start;//边的起点
int end;//边的终点
int wieght;//边的权重
}node;
class Graph{
private:
node *edge; //边的数组
int edgeNum;//边的个数
int vertexNum;//顶点的个数
int* unionset;//并查集，顶点的集合
#pragma 下面的这几个private函数都是并查集的函数
int findRoot(int node);//找根
void unionSet(int node1,int node2);//合并俩结点成为一个集合
bool isaSet(int node1,int node2);//判断俩结点在没在一个集合中
public:
Graph(int size,int vertexNum);
void create();
void sort();//冒泡法按照权值从大到小的顺序排序；
void kuscal();//kruskal算法；
void print();//输出边的数组和 顶点的集合，
};
void Graph::print(){
cout<<"unionSet-----------------------------------------------------\n";
for (int i = 0; i<vertexNum+1; i++) {
cout<<i<<":"<<unionset[i]<<endl;
}
cout<<"unionset______________________________________________________\n";
for (int i =0; i<2; i++) {
cout<<endl;
}
cout<<"edge----------------------------------------------------------\n";
for (int i = 0; i<edgeNum; i++) {
cout<<"("<<edge[i].start<<","<<edge[i].end<<","<<edge[i].wieght<<")";
}
cout<<endl;
cout<<"edge__________________________________________________________\n";
}
//看是否在同一个集合，如果在一个集合，返回True，否则返回false；
bool Graph::isaSet(int node1, int node2){
return findRoot(node1)==findRoot(node2) ? true : false;
}
//把node2添加到node1集合中
void Graph::unionSet(int node1, int node2){
int root1 = findRoot(node1);
int root2 = findRoot(node2);
unionset[root1]+=unionset[root2];
unionset[root2] = root1;
}
void Graph::sort(){
for (int i = 0; i<edgeNum -1; i++) {
for (int j = 0; j<edgeNum-1-i; j++) {
if(edge[j].wieght < edge[j+1].wieght){
int temp = edge[j].wieght;
int start = edge[j].start;
int end = edge[j].end;
edge[j].wieght = edge[j+1].wieght;
edge[j+1].wieght = temp;
edge[j].start = edge[j+1].start;
edge[j+1].start = start;
edge[j].end = edge[j+1].end;
edge[j+1].end = end;
}
}
}
print();
}
int Graph::findRoot(int node){
int root = node;
while (unionset[root] >= 0) {
root = unionset[root];
}
return root;
}
Graph::Graph(int size,int vertexNum){
edge = new node[size];
edgeNum = size;
this->vertexNum = vertexNum;
/*
1:一般来说，多申请一个，这样有利于数据的统一
*/
unionset = new int[vertexNum+1];
for (int i = 0; i<vertexNum+1; i++) {
unionset[i]= -1;
}
}
void Graph::create(){
cout<<"input edge start and end and widght\n";
for (int i = 0; i<edgeNum; i++) {
cin>>edge[i].start>>edge[i].end>>edge[i].wieght;
}
}
void Graph::kuscal(){
sort();
int edgeNum1 = 0;//找到的满足要求的边的个数
int sum = 0;//找的满足要求的边的权重和�
int i = edgeNum-1;//控制边数组的下标，从后往前取，最小值在后面
while (edgeNum1 != this->vertexNum-1 ) {
int start = edge[i].start;
int end = edge[i].end;
if( isaSet(start, end) == false){
unionSet(start, end);
edgeNum1++;
sum+=edge[i].wieght;
}
I--;
}
cout<<"sum"<<sum<<endl;
}
int main(){
Graph a(8, 6);
a.create();
a.print();
a.kuscal();
a.print();
}
image.png
输入如下：
image.png
输出如下：
image.png
网友评论