首页 > 编程语言 >最小生成树算法

最小生成树算法

时间:2022-10-02 21:13:02浏览次数:88  
标签:Prim Unknown 复杂度 最小 生成 算法 Known 顶点

最小生成树是指在一个图中,由连接所有顶点的边构成的权值之和最小的树,求最小生成树的算法主要有Prim算法及Kruskal算法,此处介绍Prim算法的基本原理。

Prim算法是一种贪心算法,不过可以证明,此算法得到的必定是全局最优解。Prim算法的基本思路如下:

  1. 将图中的所有顶点分为两个集合,KnownUnknown,初始时任意选择一个顶点放置在Known中,其余顶点位于Unknown中,算法的目标是将Unknown中的所有顶点移至Known中;
  2. 选择一条边,这条边连接的两个顶点一个位于Known中,另一个位于Unknown中,且这条边的权值是所有满足条件的边中最小的;
  3. 将这条边添加到最小生成树中,并将其连接的那个位于Unknown集合中的顶点移至Known中;
  4. 重复以上两步,直至Unknown集合为空;

算法图示:

算法图示

Prim算法的过程与Dijkstra算法很相像,故二者的程序结构也很类似。

在使用邻接表及二叉堆实现时,Prim算法的时间复杂度是 \(O(|E|log|V|)\),需要注意的是,无论对于稀疏图还是稠密图,这都是一个最优的算法复杂度。Kruskal算法的复杂度是 \(O(|E|log|E|)\),对于所有连通图来说都有 \(|E|>=|V|-1\),所以可以得出结论,Prim算法在时间复杂度上无论是对于稀疏图还是稠密图来说都是最优的,优于Kruskal算法。不过其最大缺点就是在使用二叉堆时空间复杂度会极大,对于超稠密图就很不合适了。具体定量比较可参考:

Prim、Kruskal、Prim+Heap算法效率实测

算法的实现代码有空再补上吧……

or 参考: 最小生成树的常用算法模板

标签:Prim,Unknown,复杂度,最小,生成,算法,Known,顶点
From: https://www.cnblogs.com/RioTian/p/16749468.html

相关文章

  • 面试官:生成订单 30 分钟未支付,则自动取消,该怎么实现?
    在开发中,往往会遇到一些关于延时任务的需求。例如生成订单30分钟未支付,则自动取消生成订单60秒后,给用户发短信对上述的任务,我们给一个专业的名字来形容,那就是延时任......
  • 爬山算法&&模拟退火
    constdoubledown=0.996;//降温系数constdoubleeps=1e-15;//终止温度doubleansx,ansy,answ,T;structpoint{intx,y,w;}a[Z];inlinedoubledis(doub......
  • AES加密算法原理及python实现
    AES对称加密算法  AES加密算法即密码学中的高级加密标准(AdvancedEncryptionStandard,AES),又称Rijndael加密法(2000年10月2日,比利时密码专家JoanDaemen和VincentRijmen提......
  • 在强化学习算法性能测试时使用训练好的模型运行游戏,此时如何控制实时游戏画面的帧数
    问题:在强化学习算法性能测试时使用训练好的模型运行游戏,此时如何控制实时游戏画面的帧数?  ========================================  看到很多训练好的模型与游戏交......
  • 强化学习的REIINFORCE算法和交叉熵RL算法
    注意:本文并不讲REINFORCE算法,而是讲强化学习的交叉熵算法,关于REINFORCE算法可以参看:   ==========================================   强化学习有多种分类方法,其中一......
  • BF(暴力求解算法)
    BF(暴力求解算法)即是暴力(BruteForce)算法,是普通的模式匹配算法,BF算法的思想就是将目标串T的第一个字符和主串的S的第一个字符进行匹配,若相等,则则继续匹配T串和S串的第二......
  • C++实现双向RRT算法
    C++实现双向RRT算法背景介绍RRT(Rapidly-exploringRandomTrees)是StevenM.LaValle和JamesJ.KuffnerJr.提出的一种通过所及构建空间搜索树实现对非凸高维空间快速搜......
  • 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
    链接:https://time.geekbang.org/column/article/71187目录字符串匹配算法BF算法RK算法字符串匹配算法BF算法、RK算法、BM算法、KMP算法BF算法和RK算法:单模......
  • KMP算法
    KMP算法首先kmp算法有两个字符串,一个目标串s[],一个模板串p[]我们需要对模板串进行预处理,创建一个数组ne[i]表示以p[i]为结尾的字符串和前缀相等字符串的最长长度,就是前缀......
  • 对于关键路径算法中最迟发生时间取最小值的理解
    问题产生:错误理解:当前事件的最迟发生时间vl(i)的产生跟与之直接关联的后继事件j和中间活动<i,j>有关,如果要使当前事件发生的时间“最晚”,应当取集合{j}中产生的最大......