最小生成树的两种方法(Kruskal算法和Prim算法)[通俗易懂]

关于图的几个概念定义:连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图。 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。 生成树:一个连通图的生成树是指一个连通子图,它含有图中…

大家好,又见面了,我是你们的朋友全栈君。

关于图的几个概念定义:

  • 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。
  • 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图。
  • 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。
  • 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
  • 最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 
    这里写图片描述

下面介绍两种求最小生成树算法

1.Kruskal算法

此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。 
1. 把图中的所有边按代价从小到大排序; 
2. 把图中的n个顶点看成独立的n棵树组成的森林; 
3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

这里写图片描述

2.Prim算法

此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。

  1. 图的所有顶点集合为VV;初始令集合u={s},v=V−uu={s},v=V−u;
  2. 在两个集合u,vu,v能够组成的边中,选择一条代价最小的边(u0,v0)(u0,v0),加入到最小生成树中,并把v0v0并入到集合u中。
  3. 重复上述步骤,直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点,所以最小代价边必须同步更新;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息,:

struct
{
  char vertexData   //表示u中顶点信息
  UINT lowestcost   //最小代价
}closedge[vexCounts]

这里写图片描述


3.完整代码

/************************************************************************
CSDN 勿在浮沙筑高台 http://blog.csdn.net/luoshixian099算法导论--最小生成树(Prim、Kruskal)2016年7月14日
************************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INFINITE 0xFFFFFFFF   
#define VertexData unsigned int  //顶点数据
#define UINT  unsigned int
#define vexCounts 6  //顶点数量
char vextex[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
struct node 
{
    VertexData data;
    unsigned int lowestcost;
}closedge[vexCounts]; //Prim算法中的辅助信息
typedef struct 
{
    VertexData u;
    VertexData v;
    unsigned int cost;  //边的代价
}Arc;  //原始图的边信息
void AdjMatrix(unsigned int adjMat[][vexCounts])  //邻接矩阵表示法
{
    for (int i = 0; i < vexCounts; i++)   //初始化邻接矩阵
        for (int j = 0; j < vexCounts; j++)
        {
            adjMat[i][j] = INFINITE;
        }
    adjMat[0][1] = 6; adjMat[0][2] = 1; adjMat[0][3] = 5;
    adjMat[1][0] = 6; adjMat[1][2] = 5; adjMat[1][4] = 3;
    adjMat[2][0] = 1; adjMat[2][1] = 5; adjMat[2][3] = 5; adjMat[2][4] = 6; adjMat[2][5] = 4;
    adjMat[3][0] = 5; adjMat[3][2] = 5; adjMat[3][5] = 2;
    adjMat[4][1] = 3; adjMat[4][2] = 6; adjMat[4][5] = 6;
    adjMat[5][2] = 4; adjMat[5][3] = 2; adjMat[5][4] = 6;
}
int Minmum(struct node * closedge)  //返回最小代价边
{
    unsigned int min = INFINITE;
    int index = -1;
    for (int i = 0; i < vexCounts;i++)
    {
        if (closedge[i].lowestcost < min && closedge[i].lowestcost !=0)
        {
            min = closedge[i].lowestcost;
            index = i;
        }
    }
    return index;
}
void MiniSpanTree_Prim(unsigned int adjMat[][vexCounts], VertexData s)
{
    for (int i = 0; i < vexCounts;i++)
    {
        closedge[i].lowestcost = INFINITE;
    }      
    closedge[s].data = s;      //从顶点s开始
    closedge[s].lowestcost = 0;
    for (int i = 0; i < vexCounts;i++)  //初始化辅助数组
    {
        if (i != s)
        {
            closedge[i].data = s;
            closedge[i].lowestcost = adjMat[s][i];
        }
    }
    for (int e = 1; e <= vexCounts -1; e++)  //n-1条边时退出
    {
        int k = Minmum(closedge);  //选择最小代价边
        cout << vextex[closedge[k].data] << "--" << vextex[k] << endl;//加入到最小生成树
        closedge[k].lowestcost = 0; //代价置为0
        for (int i = 0; i < vexCounts;i++)  //更新v中顶点最小代价边信息
        {
            if ( adjMat[k][i] < closedge[i].lowestcost)
            {
                closedge[i].data = k;
                closedge[i].lowestcost = adjMat[k][i];
            }
        }
    }
}
void ReadArc(unsigned int  adjMat[][vexCounts],vector<Arc> &vertexArc) //保存图的边代价信息
{
    Arc * temp = NULL;
    for (unsigned int i = 0; i < vexCounts;i++)
    {
        for (unsigned int j = 0; j < i; j++)
        {
            if (adjMat[i][j]!=INFINITE)
            {
                temp = new Arc;
                temp->u = i;
                temp->v = j;
                temp->cost = adjMat[i][j];
                vertexArc.push_back(*temp);
            }
        }
    }
}
bool compare(Arc  A, Arc  B)
{
    return A.cost < B.cost ? true : false;
}
bool FindTree(VertexData u, VertexData v,vector<vector<VertexData> > &Tree)
{
    unsigned int index_u = INFINITE;
    unsigned int index_v = INFINITE;
    for (unsigned int i = 0; i < Tree.size();i++)  //检查u,v分别属于哪颗树
    {
        if (find(Tree[i].begin(), Tree[i].end(), u) != Tree[i].end())
            index_u = i;
        if (find(Tree[i].begin(), Tree[i].end(), v) != Tree[i].end())
            index_v = i;
    }

    if (index_u != index_v)   //u,v不在一颗树上,合并两颗树
    {
        for (unsigned int i = 0; i < Tree[index_v].size();i++)
        {
            Tree[index_u].push_back(Tree[index_v][i]);
        }
        Tree[index_v].clear();
        return true;
    }
    return false;
}
void MiniSpanTree_Kruskal(unsigned int adjMat[][vexCounts])
{
    vector<Arc> vertexArc;
    ReadArc(adjMat, vertexArc);//读取边信息
    sort(vertexArc.begin(), vertexArc.end(), compare);//边按从小到大排序
    vector<vector<VertexData> > Tree(vexCounts); //6棵独立树
    for (unsigned int i = 0; i < vexCounts; i++)
    {
        Tree[i].push_back(i);  //初始化6棵独立树的信息
    }
    for (unsigned int i = 0; i < vertexArc.size(); i++)//依次从小到大取最小代价边
    {
        VertexData u = vertexArc[i].u;  
        VertexData v = vertexArc[i].v;
        if (FindTree(u, v, Tree))//检查此边的两个顶点是否在一颗树内
        {
            cout << vextex[u] << "---" << vextex[v] << endl;//把此边加入到最小生成树中
        }   
    }
}

int main()
{
    unsigned int  adjMat[vexCounts][vexCounts] = { 0 };
    AdjMatrix(adjMat);   //邻接矩阵
    cout << "Prim :" << endl;
    MiniSpanTree_Prim(adjMat,0); //Prim算法,从顶点0开始.
    cout << "-------------" << endl << "Kruskal:" << endl;
    MiniSpanTree_Kruskal(adjMat);//Kruskal算法
    return 0;
}

最小生成树的两种方法(Kruskal算法和Prim算法)[通俗易懂]

转载:勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51908175


Reference: 
数据结构–耿国华 
算法导论–第三版

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/125745.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 计算机组成原理 时钟周期_什么是指令周期机器周期和时钟周期

    计算机组成原理 时钟周期_什么是指令周期机器周期和时钟周期时钟周期:一个时钟脉冲所需要的时间。在计算机组成原理中又叫T周期或节拍脉冲。是CPU和其他单片机的基本时间单位。它可以表示为时钟晶振频率(1秒钟的时钟脉冲数)的倒数(也就是1s/时钟脉冲数,比如1/12MHz),对CPU来说,在一个时钟周期内,CPU仅完成一个最基本的动作。时钟脉冲是计算机的基本工作脉冲,控制着计算机的工作节奏。时钟频率越高,时钟周期就越短,工作速度也就越快。时钟周期在CPU的描述…

    2022年10月13日
  • 使用Python对股票数据进行数据分析(一)-计算日线行情、5日均线、10日均线行情并显示

    使用Python对股票数据进行数据分析(一)-计算日线行情、5日均线、10日均线行情并显示使用Python对股票数据进行数据分析(一)-计算日线行情、5日均线、10日均线行情并显示各种炒股软件上可以显示各种技术指标,可以帮助投资者进行技术分析。这些股市中的这些指标都是怎么计算出来的呢?这里使用python的pandas库来进行计算。后期可能使用一些专门金融分析的库,比如talib库等进行分析。一、获取数据这里需要获取的数据是股票的日线行情,这里使用tushare进行获取,以…

    2022年10月26日
  • java 获取当前时间的三种方法_java获取单层文件夹大小

    java 获取当前时间的三种方法_java获取单层文件夹大小A获取当前时间:Java代码importjava.text.SimpleDateFormat;importjava.util.Date;publicclassGetCurrentTime{/*获得当前时间*/publicstaticStringgetCurrentTime(){DatecurrentTime=newDate();SimpleDateFormatformat…

  • 计算机组成原理知识点

    计算机组成原理知识点计算机体系结构(ComputerArchitecture)主要研究硬件和软件功能的划分,确定硬件和软件的界面,哪部分功能由硬件系统来完成,哪部分功能由软件系统来完成。计算机组成原理(ComputerOrganization)是依据计算机体系结构,在确定且分配了硬件子系统的概念结构和功能特性的基础上,设计计算机各部件的具体组成,以及它们之间的连接关系,实现机器指令级的各种功能和特性,这点上说

  • Tomcat学习—Tomcat的tomcat-user.xml配置文件

    Tomcat学习—Tomcat的tomcat-user.xml配置文件

  • 密码攻略 黑客亲手打造QQ密码激活成功教程器(转)

    密码攻略 黑客亲手打造QQ密码激活成功教程器(转)密码攻略黑客亲手打造QQ密码激活成功教程器(转)[@more@]现在使用QQ的网友越来越多了。可是如果密码忘记了或嫌输入QQ密码过于麻烦,那怎么办呢。我们可以自己制作一款QQ密码器。如果你感兴趣的话。可以和我一起自己动手做一个这样的Q…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号