数据结构---最小生成树((普里姆算法)C语言看了就懂教程)

这篇具有很好参考价值的文章主要介绍了数据结构---最小生成树((普里姆算法)C语言看了就懂教程)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.概述

    普里姆算法就是“加点法”,是一种将连通网转换成最小生成树的一种算法

    在一个连通图的所有生成树中,各边代价之和最小的那颗生成树称为该连通图的最小代价生成树(MST)

2.算法逻辑:

    ①对于任意一张连通图,假设 N = (V,E)是连通网,TE就是最小生成树中边的集合

    ②生成树先从一个结点开始,U = {u0},u0就是V中的任意一点。

    ③在V-U中所有的(u,v)中找出最短一条边,并入TE中

    ④循环往复第三步就能得到最小生成树 (V,TE)---(顶点,边)

3.上述算法逻辑就是课本上的算法描述,更通俗易懂的理解如下

    普里姆算法(贪心算法)

    步骤:

    ①先将图拆解成森林

    ②以任意一个顶点为出发点,通过对到其他顶点的权值进行比较,找到最小边得到一颗树(顶点,边)集合

    ③将②中的”顶点“换成“这颗树”与其他顶点是否有更小的权值

    ④重复第③步就可以得到最小生成树

    使用实例:

    对于最小生成树的概念,可以拿生活中的地图来进行说明

    eg:假设每个城市之间都有固定的路径,固定的距离,这是就可以将其理解成一张很大的无向图,当需要去建造铁路网,得考虑到材料资金问题,时间问题,效率问题等等。。。

就是要找到连通城市网络所需要付出的最小代价的方法,就需要将城市网转换成最小生成树。

4.代码框架讲解

    如何去实现一个工程或者算法的代码,需要哪些对象(函数变量),首先的清楚需要什么功能(函数方法)实现逻辑(上述已经讲了)

    需要哪些对象(函数变量)?

    既然是连通图就得有图的数据类型       

     typedef struct
     {
           char vexs[MAXVEX];          //顶点表
           int arc[MAXVEX][MAXVEX];    //边表
           int numVertexes,numEdges;   //顶点数量
           int GraphType;              //图的类型
     }MGraph;

        既然比较子连通图中边的权值,得有存放的地方

        struct fuzhu                         //辅助数组---说到底就是算法的本质
        {
            char adjvex;                    //权值
            int lowcost;                    //坐标点
        };
        struct fuzhu closedge[MVNum];   //定义辅助队列结构体

        以上两个结构体就是主要的变量类型,其他的int、char之类的都是辅助性的

    需要什么功能(函数方法)?

        围绕算法,你需要创建一张连通图

        void CreateMGraph(MGraph *G)                //创建图列

        打印出连通图

        void output(MGraph *G)                      //输出

        需要去找权值集合中的最小值

        int Min(MGraph *G)                          //获取辅助队列中,权值集合中最小的权值

        因为是从任意一点开始就得先知道其顶点坐标

        int LocateVex(MGraph *G,char u)             //获取图表中顶点为u的顶点

        算法实现,传入任意连通图跟随机顶点,生成最小树

 void MiniMGraph_prim (MGraph *G, char u)    //选择从哪个顶点开始,随机就行没有针对性说要哪个

5.代码具体实现以及讲解

    本文只讲解对于辅助数组的用法实现,以及MiniMgraph_prim()的实现

    辅助数组其实就是个很简单的结构体而已,主要是你得知道如何去用,

    因为在创建连通图的生成过程中,两结点之间要么为权值要么就为65535,利用这点实现算法中枢。

    文字难讲清楚,而且难看,直接看图解

山东大学数据结构实验最小生成树prim算法c语言,算法,数据结构,c语言,贪心算法

 创建一个新的图列---无向连通图

山东大学数据结构实验最小生成树prim算法c语言,算法,数据结构,c语言,贪心算法

prim算法实现步骤 

山东大学数据结构实验最小生成树prim算法c语言,算法,数据结构,c语言,贪心算法

山东大学数据结构实验最小生成树prim算法c语言,算法,数据结构,c语言,贪心算法 

 辅助数组元素变化


        void MiniMGraph_prim (MGraph *G, char u)    //选择从哪个顶点开始,随机就行没有针对性说要哪个
        {
            int k;
            char u0,v0;
            int  j,i;
            k = LocateVex(G,u);
            for(j = 0;j<G->numVertexes;j++)
            if(j != k)  
            {
                closedge[j]. adjvex = u;
                closedge[j].lowcost = G->arc[k][j];
            }
            closedge[k].lowcost = 0;
            //初始化辅助结构体,将其边上的权值添加进结构体
            for(i = 1;i<G->numVertexes;i++)
            {
                k = Min(G);
                u0 = closedge[k].adjvex;
                v0 = G->vexs[k];
                printf("%c %c\n",u0,v0);
                closedge[k].lowcost = 0;
                for(j =0;j<G->numVertexes;j++)
                    if(G->arc[k][j]<closedge[j].lowcost)
                    {
                        closedge[j].adjvex = G->vexs[k];
                        closedge[j].lowcost = G->arc[k][j];
                    }          
            }
            /*
            从各组边closedge中选出最小边,并输出此边
            再判断该最小边上是否有更小的边,若有则将其顶点和权值都添加进结构体
            如此反复 就能得到最小生成树
            */
        }

    上述MiniMGraph_prim()中:

 首先找出随机顶点的坐标值以及将辅助数组进行初始化(初始化的过程就是对应辅助数列的第一步)

            k = LocateVex(G,u);
            for(j = 0;j<G->numVertexes;j++)
            if(j != k)  
            {
                closedge[j]. adjvex = u;
                closedge[j].lowcost = G->arc[k][j];
            }
            closedge[k].lowcost = 0;
            //初始化辅助结构体,将其边上的权值添加进结构体

    ①找出辅助数组最小权值的下标k,并将其(u0)adjvex和v0(G->vex[k])打印;

            k = Min(G);
            u0 = closedge[k].adjvex;
            v0 = G->vexs[k];
            printf("%c %c\n",u0,v0);

    ②更新辅助数组;

            for(j =0;j<G->numVertexes;j++)
                if(G->arc[k][j]<closedge[j].lowcost)
                {
                    closedge[j].adjvex = G->vexs[k];
                    closedge[j].lowcost = G->arc[k][j];
                }  

    ③直到所有的顶点都被判断一遍,或直到辅助数组中lostcost都为0;

山东大学数据结构实验最小生成树prim算法c语言,算法,数据结构,c语言,贪心算法

总结:

    该算法的总体难度其实并不是很难,相信你如果完全看完的话,就能明白核心点在哪

    对于struct MGraph ,这里不需要设计到指针的度用法,就只是地址的传参

    {reason:这是一个整体,他在创建时就申请了一个很大的空间,全部数据都存放在里面

    其中包含,char型的一维数组,int型的二维数组,以及几个int型数据},不要搞混了不然很容易陷入死回路

    关键在于:如何利用辅助数组去找到最小权值边,并打印该边的两个结点。



 文章来源地址https://www.toymoban.com/news/detail-775586.html

到了这里,关于数据结构---最小生成树((普里姆算法)C语言看了就懂教程)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 最小生成树(详解普里姆算法)

    首先,我们来看一下 图的一些基本知识点 : 图 :图 G=(V,E) 由顶点集 V 和边集 E 组成。每条边对应一个点对 (v,w),其中 v,w 属于 V 。如果图中的点对是有序的,那么该图就是有向图,反之为无向图。 邻接点 :若顶点 v 与 w 之间存在一条边,则认为顶点 v 与 w 邻接。 权 :图

    2024年01月19日
    浏览(81)
  • 大话数据结构-普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)

       构造连通网的最小代价生成树称为最小生成树,即Minimum Cost Spanning Tree ,最小生成树通常是基于无向网/有向网构造的。   找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。   普里姆算法,即Prim算法,大致实现过程如下:   (1) 新建数组

    2024年02月05日
    浏览(45)
  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

     想求最小生成树,我们首先得弄懂以下几个概念   连通图 :图中任意两个顶点都是连通的 极小连通子图 :既要保持图连通又要使得边数最少的子图 生成树 : 包含图中全部顶点的一个极小连通子图 连通图用通俗的话来讲就是,某一个顶点,可以 直接或者间接 (通过其他顶点

    2024年02月05日
    浏览(45)
  • 已知无向图G如下所示,使用普里姆 (Prim)算法求图G的最小生成树。 (a)请写出从顶点T出发,加到最小生成树中的边次序。 (6分) (2)说明Prim算法更适用于求哪种类型无向图的最小生 成树。(2分) (3)当图中顶点个数为n,边的个数为e时,该算法

    (a)从顶点T出发,加到最小生成树中的边次序如下: 先加入顶点T到顶点E的边,得到的最小生成树为:T-E 再加入顶点E到顶点D的边,得到的最小生成树为:T-E-D 再加入顶点D到顶点B的边,得到的最小生成树为:T-E-D-B 再加入顶点B到顶点C的边,得到的最小生成树为:T-E-D-B-C 再加

    2024年01月17日
    浏览(48)
  • prim算法(普里姆算法)详解

    了解了什么是最小生成树后,本节为您讲解如何用普里姆(prim)算法查找连通网(带权的连通图)中的最小生成树。 普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重

    2024年01月16日
    浏览(41)
  • Java高阶数据结构 & 并查集 & 最小生成树

    并查集与最小生成树 1.1 并查集的原理 在一些应用问题中,我们常常会遇到一类问题 一开始是一个人 后来新增的人可能与这个人有关系,也可能与这个人无关系。 一个人与一个人有关系,这个人与另一个人也有关系,那么三人都有关系。 有关系的和没关系的之间是不同的类

    2024年02月03日
    浏览(42)
  • 数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题,有11个城市,城市之间有一些天然气管道,铺设天然气管道需要花费不同的金额,现在要你选择其中一些天然气管道,使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图,每个城市是一个顶点,城市与城市之间的管道是

    2024年02月08日
    浏览(54)
  • C++数据结构——习题6-5 最小生成树(Prim算法)

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。已知村庄数N和可建道路数M,设初始状态下任意村庄之间没有路,请编写程序,根据输入的两村庄间修建道路的费用情况,计算这些村庄

    2024年02月09日
    浏览(81)
  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合,每个集合有一个代表,不关心谁做代表。 支持三种操作: MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(50)
  • 【数据结构】无向图的最小生成树(Prime,Kruskal算法)

    连通图 :在 无向图 中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中 任意一对顶点都是连通的 ,则称此图为连通图 强连通图 :在 有向图 中,若在每一对顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图是强连通图 生成

    2024年01月24日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包