精华内容
下载资源
问答
  • 最小生成树算法C++语言实现
    千次阅读 热门讨论
    2021-02-14 11:34:26

    最小生成树算法C++语言实现

    1. Prim

    思想:选择离当前树最近的点来扩充当前树,直至边数为n-1。因为要从候选点中选择距离最近的点,直接实现比较困难,不如转换一下,选择当前最小生成树中的点向外延伸的边中最短的那条边,使用优先队列来维护向外延伸的边,实现起来比较简单。

    #include <bits/stdc++.h>
    using namespace std;
    int n,m,a,b,v;
    struct Edge{
        int fr,to,l;
        explicit Edge(int aa=0,int bb=0,int vv=0){fr=aa;to=bb;l=vv;}
        bool operator<(const Edge& o) const{
            return this->l>o.l;
        }
    };
    vector<Edge> graph[100010];
    bool flag[100010]; // flag[i]==true means node i is in tree;
    Edge tree[100010];
    void Prim(){
        priority_queue<Edge> pq;
        flag[1]=true;
        int cnt=0;
        for(Edge e:graph[1]){pq.push(e);}
        while(cnt<n-1){
            Edge top=pq.top();pq.pop();
            if(flag[top.to]){continue;}
            flag[top.to]=true;
            tree[cnt++]=top;
            for(Edge e:graph[top.to]){
                if(!flag[e.to]){
                    pq.push(e);
                }
            }
        }
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=0;i<m;++i) {
            cin>>a>>b>>v;
            Edge e1(a,b,v),e2(b,a,v);
            graph[a].push_back(e1);
            graph[b].push_back(e2);
        }
        Prim();
        for(int i=0;i<n-1;++i){
            Edge e=tree[i];
            cout<<e.fr<<"->"<<e.to<<":"<<e.l<<endl;
        }
    }
    
    /**
    5 7
    1 2 6
    1 3 1
    1 4 7
    2 3 2
    2 4 5
    3 4 3
    3 5 4
    
     6 9
     1 2 2
     1 3 3
     2 3 6
     2 4 9
     2 5 5
     4 5 4
     3 5 1
     3 6 8
     5 6 7
     */
    
    

    2. Kruskal

    思想:贪心每次选择最小边,将两棵子树归并成一棵树,如果最小边的两个端点属于同一子树,则跳过该边。该场景符合并查集的使用场景,因此采用并查集实现。

    #include <bits/stdc++.h>
    using namespace std;
    int n,m,a,b,v;
    struct Edge{int fr,to,l;};
    bool cmp(Edge e1, Edge e2){return e1.l<e2.l;}
    Edge graph[100010];
    Edge tree[100010];
    int fa[100010];
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void merge(int x,int y){fa[find(x)]=find(y);}
    void Kruskal(){
        for(int i=1;i<=n;++i){fa[i]=i;}  // init UnionSet
        sort(graph, graph+m,cmp);
        for(int i=0,j=0;i<n-1&&j<m;++j){
            Edge curr=graph[j];
            if(find(curr.fr)!=find(curr.to)){
                tree[i++]=curr;
                merge(curr.fr,curr.to);
            }
        }
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=0;i<m;++i) {
            cin>>graph[i].fr>>graph[i].to>>graph[i].l;
        }
        Kruskal();
        for(int i=0;i<n-1;++i){
            Edge e=tree[i];
            cout<<e.fr<<"->"<<e.to<<":"<<e.l<<endl;
        }
    }
    
    更多相关内容
  • matlab最小生成树算法

    2018-06-20 23:27:43
    matlab算法,可以解决最小生成树算法以及类似问题关于最小生成树,学过图论的都懂,这里就不做介绍。 下面是一个例题,附有Kruskal算法和Prim算法。
  • 输入:城市个数N 输出:建设通信网络的结构和最低成本(距离即成本) 说明:主函数调用prepare函数准备城市坐标及各城市间距离等数据,并调用最小生成树算法primMST primMST算法根据城市网络图获得最小生成树
  • 最小生成树算法及实例.zip
  • 最小生成树的构造,以及求最小生成树的 普利姆算法和克鲁斯卡尔算法,C++实现算法
  • 最小生成树算法

    千次阅读 2021-04-10 12:50:15
    最小生成树算法生成树的概念最小生成树算法Prim算法Kruskal算法 生成树的概念 若图是连通的无向图或强连通的有向图,则从其中任一顶点出发,调用一次dfsdfsdfs或者bfsbfsbfs后,可以系统的访问图中所有顶点。 若图...

    生成树的概念

    • 若图是连通的无向图或强连通的有向图,则从其中任一顶点出发,调用一次 d f s dfs dfs或者 b f s bfs bfs后,可以系统的访问图中所有顶点。
    • 若图是有根的有向图 ,则从根出发,调用一次 d f s dfs dfs或者 b f s bfs bfs后,可以系统的访问图中所有顶点。

    在上述情况之下,图中所有顶点加上遍历过程中经过的所有边所构成的子图称为原图的生成树

    若图是不连通的的无向图和不是强连通的有向图,从其中任一顶点出发,调用一次 d f s dfs dfs或者 b f s bfs bfs后,不能系统的访问图中所有顶点,只能得到以出发点为根的连通分支(或者强连通分支)的生成树。若想访问其他顶点则需要以一个没有访问过的点作为起点,再次调用 d f s dfs dfs或者 b f s bfs bfs,这样就得到了生成森林

    很显然,一个图的生成树并不是唯一的,不同的搜索方法或者同一个搜索方法但出发点不同,都可以得到不同的生成树。
    可以证明:具有n个顶点的带权连通图,其对应的生成树有n-1条边。

    最小生成树算法

    举例:给出一张有五座城市的地图。
    在这里插入图片描述
    用DFS遍历得到的生成树:
    在这里插入图片描述
    用BFS遍历得到的生成树:
    在这里插入图片描述
    上述俩种生成树的权和分别为20和33,我们不难发现,最小的生成树权和应该为19,因此上述俩种并不是最小生成树。那如何得到最小生成树呢?
    在这里插入图片描述
    出发点:具有n个顶点的带权连通图,其对应的最小生成树都有n-1条边。
    下列俩种算法都是基于贪心思想的算法。
    时间复杂都为O(n*n)。

    Prim算法

    思路如下:

    1. 设置一个顶点集合S和一个边集合TE,S和TE的初始状态皆为空集。
    2. 选定图中的任意顶点K,从K开始生成最小生成树。(K加入集合S)。
    3. 重复下列操作,直到选取了n-1条边为止。
      (1)选取一条权最小的边(X,Y),要求是X要集合S的元素,Y不是集合S的元素。
      (2)将顶点加入到集合S中,将边(X,Y)加入集合TE中。
    4. 得到最小生成树T,T=(S,TE)。

    Kruskal算法

    思路如下:

    1. 设最小生成树为T,T=(S,TE),TE初始状态为空集。
    2. 将图中的边权从小到大依次排序。
    3. 选取权最小的边,若这条边没有使T构成回路,就将这条边加入TE中(T保留了这条边);若构成回路,则舍弃,不能加入TE中。
    4. 再选取最小边,重复执行第三步,直到TE中包含n-1条边为止,最后的T即为最小生成树。

    这个算法的难点在于,在选取权最小的边后,如何判断该边有没有使T构成回路。这里推荐一种方法:

    将n个顶点划分为n个集合,就是每个集合只有一个顶点,表明他们之间互不相同,各自为无回路的连通分支。当选取一条边后:

    • 若这条边俩个顶点不属于同一集合,则表明了改边连通了俩个不同的连通分支,又因为每个连通分支都是无回路的,所以连通俩个连通分支后,也无法形成回路,所以该边保留,作为T的一条边。然后把这条边的俩个顶点所在集合合并为一个集合,构成一个新的无回路的连通分支。
    • 若这条边俩个顶点不属于同一集合,则舍弃,因为同一个集合中的顶点是连通无回路的,若加入一条俩个顶点都属于本集合的边,必会形成回路
    展开全文
  • 算法分析与设计之Prim 学院软件学院 学号201421031059 吕吕 一问题描述 Prim的定义 Prim算法是贪心算法的一个实例用于找出一个有权重连通图中的最小生成树即具有最小权重且连接到所有结点的树(强调的是树树是没有...
  • 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小。这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文...
  • 数学建模常用经典算法集合均已成功编译-最小生成树算法MSTA.rar 数学建模常用经典算法集合(均已成功编译) 有偿代做,如有需要请联系QQ 1170906655,中介勿扰! 层次分析算法AHP.rar ...
  • 具体讲解请参考最小生成树算法,大佬写的非常易懂 参考资料:大话数据结构 以下是java代码实现 创建一个关于图的类 import java.util.Scanner; /** 1. @author Aaron 2. @date 2020/3/29 - 17:48 */ public class ...
  • 单元实验五------最小生成树V2V2V2V2V3V1V4V3V3V3V1V1V1V4V4V4V6V6V6V6V5V5V5V5生成树的概念生成树一个连通图的生成树是一个极小连通子图它含有图中全部顶点但只有足以构成一棵树的n-1条边生成树不唯一生成树V1V...
  • 针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim,PP)算法,基于此提出了前端驱动的并行MST算法——PB(PP Bor(u)vka)算法,并论证了PB算法的正确性。...
  • 根据Prim最小生成树算法的设计思想,设计了独特CloseEdge型closedge向量表示U到V-U集合中的边,用上三角法建立了无向图的邻接多重双向链表,构造了链接closedge向量和邻接多重双向链表表结点的VU集合双向链。...
  • 最小生成树 生成树与生成森林 最小生成树 小结与作业 生成树 一定义 图G生成树是G极小连通子图即包含G中所有顶点n与n-1条边连通子图 生成树 V1 V2 V3 V4 V5 V8 V6 V7 V1 V2 V4 V8 V5 V3 V6 V7 V1 V2 V3 V4 V5 V8 V6 ...
  • 主要介绍了最小生成树算法C语言代码实例,有需要的朋友可以参考一下
  • 欧几里得最小生成树算法通常以二次计算复杂性运行,这对于大规模的高维数据集不切实际。 在本文中,我们针对高维数据提出了一种新的两级近似欧几里德最小生成树算法。 在第一级中,我们对给定的数据集执行离群值检测...
  • 最小生成树算法之Prim(普里姆)算法

    千次阅读 2021-07-20 17:13:08
    最小生成树的可以通过Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。 Prim算法基本介绍: Prim算法又称为"加点法",每次找出距离(此处的距离指的是距离最小生成树的距离,若此处无法理解,可直接跳过,看完下面...

    最小生成树的可以通过Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。

    Prim算法基本介绍:

    Prim算法又称为"加点法",每次找出距离(此处的距离指的是距离最小生成树的距离,若此处无法理解,可直接跳过,看完下面例子就能理解)最小的边对应的点。算法逐渐从某一个顶点s开始,逐渐将n个点纳入最小生成树中。

    Prim算法基本步骤:

    第一步:设图中所有顶点的集合为V,u代表已经加入最小生成树的顶点的集合,v代表未加入最小生成树的顶点的集合,最由于从某点s开始,因此u={s},v={V-u}

    第二步:在两个集合u,v中选择一条代价最小的边,将在v中连接这条边的那个顶点x加入到最小生成树顶点集合u中,并且更新与x相连的所有邻接点

    第三步:重复上述步骤,直到最小生成树顶点集合u中有n个顶点为止


     Prim算法步骤演示,以下图为例:min数组代表,每个顶点到最小生成树的距离,以0为起点,0到最小生成树的距离就为0

      1.初始化:u={0},v={1,2,3,4,5,6},0加入到最小生成树集合u中,将0设置为蓝点,紧接着更新与0连接的邻接点1和3,此时0是最小生成树的一部分,1到最小生成树的距离为8,3到最小生成树的距离为5。

      2.此时u={0},v={1,2,3,4,5,6},在u,v两个集合中选择一条代价最小的边,下图为例就是5,根据算法步骤,将在v中连接这条边的顶点3加入到最小生成树集合u中,此时u={0,3},v={1,2,4,5,6}。然后更新与3连接的所有顶点到最小生成树的距离,1到最小生成树的距离更新为3,5到最小生成树的距离更新为7,6到最小生成树的距离更新为15

      3.此时u={0,3},v={1,2,4,5,6},在u,v两个集合中选择一条代价最小的边,下图为例就是3,根据算法步骤,将在v中连接这条边的顶点1加入到最小生成树集合u中,此时u={0,3,1},v={2,4,5,6}。然后更新与1连接的所有顶点到最小生成树的距离,2到最小生成树的距离更新为12,4到最小生成树的距离更新为10

      4.此时u={0,3,1},v={2,4,5,6},在u,v两个集合中选择一条代价最小的边,下图为例就是7,根据算法步骤,将在v中连接这条边的顶点5加入到最小生成树集合u中,此时u={0,3,1,5},v={2,4,6}。然后更新与5连接的所有顶点到最小生成树的距离,2到最小生成树的距离更新为2,4到最小生成树的距离更新为9

      5.此时u={0,3,1,5},v={2,4,6},在u,v两个集合中选择一条代价最小的边,下图为例就是2,根据算法步骤,将在v中连接这条边的顶点2加入到最小生成树集合u中,此时u={0,3,1,5,2},v={4,6}。然后更新与2连接的所有顶点到最小生成树的距离,4到最小生成树的距离更新为6

      6.此时u={0,3,1,5,2},v={4,6},在u,v两个集合中选择一条代价最小的边,下图为例就是6,根据算法步骤,将在v中连接这条边的顶点4加入到最小生成树集合u中,此时u={0,3,1,5,2,4},v={6}。然后更新与4连接的所有顶点到最小生成树的距离,发现4没有邻接点可以更新

      6.此时u={0,3,1,5,2,4},v={6},在u,v两个集合中选择一条代价最小的边,下图为例就是15,根据算法步骤,将在v中连接这条边的顶点6加入到最小生成树集合u中,此时u={0,3,1,5,2,4,6},v={}。然后更新与6连接的所有顶点到最小生成树的距离,发现6没有邻接点可以更新

     

    Prim算法执行完成后得到的最小生成树为:

    最终,将min中的值进行求和,结果为0+3+2+5+6+7+15=38,因此MST的值为38。有兴趣的朋友可以以此题为例,利用Kruskal算法求出最小生成树😊😊。

    你若盛开,蝴蝶自来;你若精彩,天自安排!算法学习贵在坚持,各位小伙伴们要坚持噢!如果对于以上博文有任何疑问,可以联系本人。wechat:Q1313135😄

     

     

    展开全文
  • 用C语言创建邻接表,存储各个节点的权值和信息,通过prim算法求出最小生成树
  • 确定顶点u在G中的位置;建立链接矩阵;队列初始化;确定顶点u在头结点向量中的位置;建立链接表;整个图深度优先遍历;整个图广度优先遍历;构造最小生成树
  • 针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法...
  • python实现prim 最小生成树算法 源码
  • 矩阵及最小生成树算法借鉴.pdf
  • 主要介绍了C++使用Kruskal和Prim算法实现最小生成树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 克鲁斯卡尔算法的基本思想是以边为主导地位,始终选择当前可用(所选的边不能构成回路)的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来...
  • 最小生成树算法、包括Kruskal算法和Prim算法,使用C# WinForm实现,示例选用算法导论第三版中的示例
  • 针对网络设计和组合优化中的度约束最小生成树问题,通过引入分裂图以及分裂数的概念,给出...并在此基础上提出了一种关于v0的最小度约束条件下的最小生成树算法,最后对算法的正确性给出了证明。算例表明了算法的有效性。
  • 并行版本的 Kruskal 最小生成树算法使用辅助线程的分析与实现 该项目提供了对用于解决最小生成树图问题的 Kruskal 算法的分析和调查。 找到图形的最小生成树对于在许多环境中优化和降低成本非常重要,例如计算机网络...
  • 算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,714
精华内容 57,085
关键字:

最小生成树算法

友情链接: Ergodic_Capacity_CDF.rar