图的最小生成树——Kruskal算法-程序员宅基地

Kruskal算法的思想如下

  1. 假设有n个顶点的连通图。首先先构造有顶点构成的集合0,每个顶点都是一个集合,不含有任何边。
  2. 在边找一个最小权值的边
  3. 判断这个边的俩个顶点是否来自于两个不同的集合,若是就将它俩归并为一个集合,然后将这个边添加到要构成的图的集合中。
  4. 直到上述的边的个数为顶点个数-1;否则,重复2-3;
    算法构成树的过程如下:

如a图所示的图,下面是最小生成树的构造过程
image

(a)

image

(b)

image

(c)

image

(d)

image

(e)

image

(f)

image

在这里判断一个边的两个顶点是不是属于同一个集合,采用的是并查集的方式来实现

并查集的基本思想如下:

并查集可以用数组来和树来实现,在这里先讲树来实现。
1:树实现并查集:
属于同一个集合的结点拥有同一个根,图示如下:
image
上面的树中这些元素都属于一个集合,他们的根元素是1;
image
上面树中元素属于都属于一个集合,他们的根元素都是11;
两个集合合并就是将一个集合连在另一个集合的根元素的下面就好了。如下图所示:
image
那在合并集合的时候怎么合并集合呢?有没有想过,如下图所示的集合
image
一个树的高度很大,一个树的高度很小,这俩个集合在合并的时候要把高度小的集合合并在高度大的集合中。因为在合并集合中的元素的时候,首先要查找这个结点属于那个结点,若是将高度高的集合合并在高度小的集合中,就会增加查找的时间,增加程序的时间复杂度。
数组实现并查集
基本思想就是,在属于一个集合的数据都用一个数据来表示就好,在合并集合的时候,就将两个集合用一个数据来表示就好了,
如下图:

image
有0——7个数据;刚开始的时候他们都是一个集合,单独的个体,每个的根都是自己本身,-1表示他们都是单独个个体,是个根,在查找根结点的时候就是一个判断依据,只要对应的数据项是负数,那就说明这个是根;现在将1和2合并为一个集合如下图:
image
将1对应数据项和2对应的数据项合并在一起,放在1对应的数据项中,在这里面就是-1+-1;将2对应的数据项改为1,表示它的根现在是1;这就是一个集合。
现在将4,5归为一个集合如下图:

image
原理和上面的一样
现在讲3添加到2所集合中如下图:
image
首相查找2的根,发现是1,然后在查找3的根,发现是3,然后在1对应的数据项中加上3对应的数据项。也就是-2+-1;然后将3对应的数据项改为-1;
现在将5所在的集合和3所在的集合合并在一块如下图:
image
先查找5所在的根结点,发现是是4;现在在查找3所在的结点,发现是1;然后还是是和之前一样相加。将4对应的数据项和1对应的数据项相加,合并两个根就好,然后将4对应的数据项改为1;
现在6加到5所在的集合中如下图:
image
查找5所在的集合,5对应的数据项是4,4对应的数据项是1,1对应的数据项是负数,说明这个是根,然后还是相加,还是合并;就好了

好了,并查集讲完了接下来就是树了
算法的流程图如下:
_
程序如下:

#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

输入如下:
image

输出如下:
image

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_33989058/article/details/89584454

智能推荐

【bzoj3747】[POI2015]Kinoman-程序员宅基地

文章浏览阅读59次。题解:水题从左向右维护以每一个作为右端点的最大值线段树维护代码:#include <bits/stdc++.h>using namespace std;#define rint register ll#define IL inline#define rep(i,h,t) for (rint i=h;i<=t;i++)#define..._从左向右维护以每一个作为右端点的最大值 设记录第 i 天的电影下次播放时间 枚举

Linux用户管理详解_linux登录qq是什么意思-程序员宅基地

文章浏览阅读448次。Linux用户管理用户基本概念什么是用户用户指的是能够正常登录Linux或Windows系统,比如:登录QQ的用户、登入王者荣耀的用户、等等[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nz1edsjq-1626145230283)(C:\Users\李开开\AppData\Roaming\Typora\typora-user-images\image-20210712171546940.png)]为什么需要用户系统上的每一个进程(运行的程序),都_linux登录qq是什么意思

Unity中协程里Animator获取状态一些笔记_getanimatortransitioninfo-程序员宅基地

文章浏览阅读4.5k次,点赞4次,收藏7次。最近用Animator获取状态各种获取错误,所以记一下笔记Animator中可以获取三种不同的状态:GetCurrentAnimatorStateInfo 获取正确的状态机状态GetNextAnimatorStateInfo 获取下一个状态机的状态GetAnimatorTransitionInfo 获取状态机的过渡状态动画同步是在帧最前,而协程是在帧的最后调用。所以切换状态后在协程获取状..._getanimatortransitioninfo

LATEX 中参考文献顺序_spphys.bst-程序员宅基地

文章浏览阅读924次。\bibliography{report} % bibliography data in report.bib\bibliographystyle{unsrt} % makes bibtex use spphys.bstunsrt 表示按照引用的先后顺序进行排序_spphys.bst

Linux下部署maven-web项目,包括JDK安装、TOMCAT安装、MYSQL安装详细解释-程序员宅基地

文章浏览阅读335次。为什么80%的码农都做不了架构师?>>> ..._linux系统搭建maven+tomcat+mysql

effective stl 第18条: 避免使用vector<bool>-程序员宅基地

文章浏览阅读354次。vector不是容器,并且它不存储bool,因为他是按照位来存储的,即一个bool只占一个二进制位。假设有vector v;则&v[0]会引起编译错误。如果不使用&v[0]可以使用vector,否则,可以用deque 和bitset来替代_避免使用vector

随便推点

signature=714e576fcd503d3d5c4bb0e0722ca7f2,System and method for the secure enrollment of devices wi...-程序员宅基地

文章浏览阅读100次。摘要:Enrolling devices with a clearinghouse server for Internet telephony and multimedia communications. Enrollment can be the process of taking a network device (such as a router, gateway, gatekeeper, ...

《iOS 9 开发指南》——第1章,第1.3节工欲善其事,必先利其器——搭建开发环境...-程序员宅基地

文章浏览阅读202次。本节书摘来自异步社区《iOS 9 开发指南》一书中的第1章,第1.3节工欲善其事,必先利其器——搭建开发环境,作者 管蕾,更多章节内容可以访问云栖社区“异步社区”公众号查看1.3 工欲善其事,必先利其器——搭建开发环境iOS 9 开发指南图片 2 知识点讲解:光盘:视频知识点第1章搭建开发环境.mp4学习iOS 9开发也离不开好的开发工具的帮助,如果使..._(1)下载完成后单击打开下载的“.dmg”格式文件,然后双击xcode文件开始安装。

iView 3.3.2 发布,基于 Vue.js 的企业级 UI 组件库-程序员宅基地

文章浏览阅读115次。开发四年只会写业务代码,分布式高并发都不会还做程序员? iView 3.3.2 发布了,iView 是一套基于 Vue..._iview 3.2.2

详解not in与not exists的区别与用法(not in的性能并不差!)-程序员宅基地

文章浏览阅读93次。2019独角兽企业重金招聘Python工程师标准>>> ..._predicate not in查询

SpringBoot整合Spring Data JPA、MySQL、Druid并使用Mockito实现单元测试_spring jpa mock-程序员宅基地

文章浏览阅读4.7k次,点赞3次,收藏7次。SpringBoot整合Spring Data JPA、MySQL、Druid并使用Mockito实现单元测试_spring jpa mock

java 解析excel金额_java解析Excel(xls、xlsx两种格式)-程序员宅基地

文章浏览阅读441次。package poi;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.IOException;import java.io.InputStream;import java.util.ArrayList;import java.util.LinkedHashMap;import j..._java getcellformatvalue

推荐文章

热门文章

相关标签