最小生成树——prim算法实现

这篇具有很好参考价值的文章主要介绍了最小生成树——prim算法实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

案例引入

N个城市之间需要铺设一张交通网,使任意两个城市间都有交通路线直达,现已知各个城市之间铺设道路的经济成本,问该如何求算铺网的最低经济成本?为求算最低经济成本,可以假设N个城市就是连通网G的N个顶点,而求算最低成本问题可以转化为在N个城市间找到N-1条边,使这些边的权值之和达到最小。在N个顶点之间可以生成许多棵不同的生成树,而最合理的交通网就是N-1条边权值之和最小的生成树。

最小生成树定义

在一个连通网所有生成树当中,各边权值之和最小的那棵生成树就叫做连通网的最小代价树,简称最小生成树。

MST性质

在构造最小生成树中,难免脱离不了对MST性质的应用。

该性质的定义为:假设U为连通网G=(V,E)中V的非空子集合,若(u,v)是一条权值最小的边,其中最小生成树——prim算法实现,那么必定存在一棵G的最小生成树包含(u,v)。

反证法:假设G的任意一棵最小生成树都不包含(u,v),设T为G的一棵最小生成树,那么必定存在(u1,v1)为T的一条边,且最小生成树——prim算法实现 .此时若在T中加入(u,v),那么新树newT一定存在环(在T中U集与V-U集分别可以构成两个连通分量),由于最小生成树——prim算法实现,可知u与u1在U集中是连通的,v与v1在V-U集中也是连通的,那么去掉(u1,v1)则将消除树的环,同时(u,v)可使U与V-U这两个连通分量重新组合成为一棵生成树。由于(u,v)的权值比(u1,v1)大,故(u,v)必定存在于某一棵最小树中。证明完毕!

普里姆算法

算法思路

该算法也称为“加点法”,即每次都选取一条权值最小的边(u,v)加入到最小生成树中,其中最小生成树——prim算法实现,使v加入到U中并且更新U到V-U各个顶点的最小权值边;重复上述步骤,直到V=U为止。

我们可以将U看成一棵树,该树到V-U的各个顶点的权值最小边由U中的某个顶点决定,比如求算U到v的权值最小需要逐一比较U中的已有顶点到v的距离选取到达v的距离最小的顶点u,规定(u,v)为U到V-U中顶点v的权值最小边

普里姆算法的构造过程

假设N=(V,E)是连通网,TE是N上最小生成树的最小边集合。

  1. 初始化U={u0},TE={空},最小生成树——prim算法实现;

  1. 选取U到V-U的最小权值边(u,v),将v加入到U中,(u,v)加入TE。由于v的加入,需要更新U到V-U的最小权值边;

  1. 重复步骤(2),直到U=V,构造结束。

注意事项:假如存在两条权值相同的最小边,则任意选取一条边加入TE。

辅助数组

由于需要选取U到V-U的最小权值边,故需要借助一个辅助数组Assistarr[mvnum]记录U到V-U的各个最小权值边。其中数组下标顶点在邻接矩阵中的下标(待会用邻接矩阵作为连通网的存储结构),adject表示U到V-U最小权值边(u,v)中的顶点u,lowcost表示边(u,v)的最小权值,其中lowcost==0表示顶点已在U中,无需再次加入。

代码实现

//文件名为:AMGraph.h
#pragma once
#include<iostream>
using namespace std;

//先实现邻接矩阵的搜索算法
#define Mvnum 100  //最大顶点数
typedef char VerType;  //顶点数据类型
typedef int ArcType;  //边的数据类型
typedef struct AMGraph {
    int vexnum, arcnum;
    VerType vexs[Mvnum];  //顶点信息表
    ArcType arcs[Mvnum][Mvnum];   //邻接矩阵
}AMGraph;
//创建无向网
void CreateUDN(AMGraph& G);
//文件名:AMGraph.cpp
#include"AMGraph.h"
//用邻接矩阵创建无向网
void CreateUDN(AMGraph& G)
{
    //表示无穷大,以方便生成最小生成树
    int inf = 999999999;
    //输入顶点与边的个数,图的第一部分信息
    cin >> G.vexnum >> G.arcnum;
    //判断合法性
    if (G.vexnum > Mvnum || G.arcnum > (G.vexnum - 1) * G.vexnum / 2)
    {
        cout << "所输入信息非法" << endl;
        return;
    }
    //紧接着输入顶点的信息,图的第二部分信息
    for (int i = 0;i < G.vexnum;i++)
    {
        cin >> G.vexs[i];
    }
    //将图的边初始化,权值全部置为inf,inf表示无穷大
    for (int i = 0;i < G.vexnum;i++)
    {
        for (int j = 0;j < G.vexnum;j++)
            G.arcs[i][j] = inf;
    }
    //输入权值
    for (int i = 0;i < G.arcnum;i++)
    {
        //输入v1,v2作为边(v1,v2)的顶点以及边之间的权值w
        //编号从0开始
        int v1, v2, w;
        //此处省略了查找v1,v2编号的过程
        cin >> v1 >> v2 >> w;
        //时刻关注合法性
        if (v1 == v2 || v1 >= G.vexnum || v2 >= G.vexnum
            || v1 < 0 || v2 < 0)
        {
            i--;
            continue;
        }
        if (G.arcs[v1][v2] != inf)
        {
            i--;
            continue;
        }
        //输入边的权值
        G.arcs[v1][v2] = G.arcs[v2][v1] = w;
    }
    //创建完毕
}
//文件名:prim.h
#pragma once
#include"AMGraph.h"

//定义辅助数组
typedef struct closedge {
    //最小边(u,v)在U中的顶点
    VerType adject;
    //U到k的最小权值
    ArcType lowcost;
}closedge;

//普里姆算法声明
void MiniSpanTree_Prim(const AMGraph& G, VerType u);

//查找下标函数
int LocateVex(const AMGraph& G, VerType u);

//找权值最小边,返回其在辅助数组中的下标
//注意数组名本身就是一个常量地址,不能传引用
int Findminarc(const AMGraph& G, const closedge* Assistarr);
//文件名:prim.cpp
#include"prim.h"

//辅助数组
closedge Assistarr[Mvnum];

//查找下标函数
int LocateVex(const AMGraph& G, VerType u)
{
    for (int i = 0;i < G.vexnum;i++)
    {
        if (G.vexs[i] == u)
            return i;
    }
    //表示没有找到,一般都不会出现这种情况
    return -1;
}

//找权值最小边,返回其在辅助数组中的下标
int Findminarc(const AMGraph& G, const closedge*Assistarr)
{
    int mark = 999999999;
    int k = 0;
    for (int i = 0;i < G.vexnum;i++)
    {
        //排除已经在U中的顶点,该顶点下标为i
        if (Assistarr[i].lowcost != 0)
        {
            if (mark > Assistarr[i].lowcost)
            {
                mark = Assistarr[i].lowcost;
                k = i;
            }
        }
    }
    return k;
}

//实现普里姆算法,针对连通图而言
void MiniSpanTree_Prim(const AMGraph& G, VerType u)
{
    //查找到u的下标,更新Assistarr数组的数据
    int k = LocateVex(G, u);
    if (k == -1)
    {
        cout << "顶点不存在" << endl;
        return;
    }
    //更新Assistarr数组
    for (int i = 0;i < G.vexnum;i++)
    {
        if (i != k)
        {
            //最小边(u0,v0)在U上的顶点最初都为u
            Assistarr[i].adject = u;
            //最小边的权值最初都为(u,v0)
            Assistarr[i].lowcost = G.arcs[k][i];
        }
    }
    //规定,如果Assistarr[i].lowcost ==0,则表示下标为i的顶点
    //已经在U中
    //顶点u一开始就在数组中,故Assistarr[k].lowest = 0;
    Assistarr[k].lowcost = 0;
    //紧接着,将剩余的n-1个顶点加入到U中
    for (int i = 1;i < G.vexnum;i++)
    {
        //找到权值最小边(u,v),u在U中,v在V-U中,因此只需要放回最小边在
        //数组中的下标k
        int k = Findminarc(G,Assistarr);
        //在U中的顶点
        VerType u0 = Assistarr[k].adject;
        //通过下标k在vexs数组中找到其顶点值
        VerType v0 = G.vexs[k];
        //打印最小生成树的一条边
        cout << u0 << "--" << v0 << endl;
        //将下标为k的顶点加入到U中
        Assistarr[k].lowcost = 0;
        //更新最小权值边
        for (int j = 0;j < G.vexnum;j++)
        {
            //G.arcs[k][j]表示(k,j)的权值,Assistarr[j].lowcost
            //表示目前U中的顶点到V-U下标为j的最小权值
            if (G.arcs[k][j] < Assistarr[j].lowcost)
            {
                Assistarr[j].lowcost = G.arcs[k][j];
                Assistarr[j].adject = G.vexs[k];
            }
        }
    }
}

测试

void test01()
{
    AMGraph G;
    CreateUDN(G);
    MiniSpanTree_Prim(G, G.vexs[0]);
}

int main()
{
    test01();
    return 0;
}

测试结果

最小生成树——prim算法实现

算法分析

在上述算法的二层循环中,第一层循环旨在将n-1条边加入到TE,故需要循环n-1次。同时,每次找最小权值边与更新最小权值边都需要扫描n次,因此时间复杂度为O(n^2)。算法的时间复杂度与顶点的个数有关,与图的存储结构无关,因此prim算法适合于稠密图。另外,由于辅助数组也会产生额外的内存空间,故空间复杂度为O(n)。文章来源地址https://www.toymoban.com/news/detail-481682.html

到了这里,关于最小生成树——prim算法实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 考研算法复试刷题19天:Prim算法求最小生成树 【prim,最小生成树】

    参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com)  总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢? 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它

    2024年02月07日
    浏览(64)
  • 贪心算法:最小生成树Prim算法

    👨‍🎓作者简介:一位喜欢写作,计科专业大二菜鸟 🏡个人主页:starry陆离 🕒首发日期:2022年5月31日星期二 🌌上期文章:动态规划:多重背包问题 📚订阅专栏:算法分析与设计 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦 这是大一暑假的c笔记,再一次写pri

    2024年02月01日
    浏览(51)
  • 最小生成树—Prim算法

    我们要讨论的问题是如何在一个 无向图 中找到它的最小生成树,虽然这个问题对有向图也有意义,但是处理起来更麻烦。 一个无向图 G 的最小生成树就是连接 G 上所有顶点的边构成的树,且这些边的总权值最低。当且仅当图是 连通的 才有最小生成树。 在无向图的最小生成

    2024年02月09日
    浏览(49)
  • Prim算法求最小生成树

    给定一张边带无权的无向图G = (V, E), n = |V|, m = |E|。由V中全部n个顶点和E中n - 1条边构成的无向连通子图被称为G的一课生成树。边的权值之和最小的生成树被称为无向图的最小生成树。 Prim算法总是维护最小生成树的一部分。最初,Prim算法仅确定1号节点属于最小生成树

    2024年02月12日
    浏览(43)
  • 最小生成树(Prim算法,Kruskal算法)

    (1)生成树: 如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树 (2)最小生成树(minimal spanning tree): 在一个图所有生成树中,代价最小的生成树称为最小生成树 (3)生成树的代价: 在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

    2024年02月08日
    浏览(44)
  • 最小生成树——普利姆(Prim)算法

    构成连通网的最小代价生成树称为最小生成树(Minimun Cost Spanning Tree). 最小生成树可以运用到生活中,假如你是一位工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大值如下图:  其中 V0~V8 是村庄,之间连线的数字表示村与村间的可通达的直线距离,比如

    2024年02月04日
    浏览(42)
  • 图的最小生成树-Prim算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Prim算法。 【输入形式】 输入图的顶点序列及图的边的情况。如样例所示。边的输入以输入-1,-1,-1,作为结束。 0,1,6 表示对应的顶点及边是:

    2024年02月08日
    浏览(52)
  • 最小生成树——Prim算法(详细图解)

    目录  最小生成树的概念   经典题目 prim算法简介  prim算法解析 (详细图解)  代码实现  代码实战 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此的边权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的

    2023年04月09日
    浏览(41)
  • 最小生成树(Prim算法与Kruskal算法)

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小生成树。 例如下图中①、②、③都是左侧图的生成树,但③是构造连通网的最小代价,所以③是该图的最小生成树。 P

    2024年02月05日
    浏览(57)
  • 最小生成树—Kruskal算法和Prim算法

    连通图:在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任 意一对顶点都是连通的,则称此图为连通图。 生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点 和n-1条边。 最小生成树:构成生成树的

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包