首页 > 其他分享 >最小生成树

最小生成树

时间:2022-10-24 11:23:04浏览次数:75  
标签:原图 连通 Prim 最小 生成 权值

1.最小生成树定义:

一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。

通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离

将最小生成树拆分成: 最小 生成 树

树:
• 树中没有环
• 所有的顶点都要在树中
• 对于N条顶点,有N-1条边

最小:
一个图,可以有很多生成树,我们把一棵树的权值相加,得到权值和。因此不同的生成树就会有不同的权值和,而最小生成树就是权值和最小生成树。

普利姆算法(Prim)

     朴素版Prim   O(n^2)      稠密图  这个常用

     堆优化版Prim  O(mlogn)   稀疏图   不常用

克鲁斯卡尔算法(Kruskal)  O(mlogm)      稀疏图这个常用

 

朴素版Prim(与dijkstra相似)

    dis [ i ] <- 很大数

    for 循环,迭代n次

      t <- 找到集合外距离集合最近的点

      用t 更新其他点到集合的距离

      Str [ t ] = true

 

 

 

 

 

 

标签:原图,连通,Prim,最小,生成,权值
From: https://www.cnblogs.com/lyhjzx/p/16820864.html

相关文章

  • ES6生成器函数2
    //模拟获取用户数据订单数据和商品数据functiongetUsers(){setTimeout(()=>{letdata="用户数据";//......
  • ES6生成器
    //生成器就是一个特殊的函数function*gen(params){console.log("111");yield'两只老虎';console.log("......
  • php生成器Generator以及yield到底是什么?
    2022年10月14日08:23:35yield关键字生成器函数的核心是yield关键字。它最简单的调用形式看起来像一个return申明,不同之处在于普通return会返回值并终止函数的执行,而yiel......
  • 证书生成(keystore、truststore、.crt、.key)
    https://blog.csdn.net/leadseczgw01/article/details/88844413https://blog.csdn.net/qq_28450911/article/details/114120752?spm=1001.2101.3001.6661.1&utm_medium=di......
  • 中国制霸生成器「GitHub 热点速览 v.22.42」
    火遍推特的中国制霸生成器本周一开源就占据了两天的GitHubTrending榜,不知道你的足迹遍布了多少个省份呢?同样记录痕迹的kanal用了内存读写方式解决了Rust的消息处理......
  • 无向图中 生成树,完全图,连通图 的区别
    图按照有无方向分为无向图和有向图。无向图由定点和边构成。有向图由定点和弧构成,弧有弧尾和弧头之分。 如果任意两个顶点之间都存在边叫做完全图。......
  • PriorityQueue 最小堆&& treemap
    优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(naturalorder......
  • 生成requirements.txt
    requirements.txt文件requirements.txt文件是项目的依赖包及其对应版本号的信息列表,即记载你这个项目所安装的依赖。作用:用来重新构建项目或者记录项目所需要的运行环境......
  • IDEA生成jar工具包
    使用IDEA生成jar工具包使用IDEA生成jar工具包,通过导入的方式在其它项目中使用。注意:此jar包是非执行jar包,只能作为工具包来使用。打包流程1.点击Build-->BuildMo......
  • Java生成验证码图片
    生成验证码/***验证码工具类**@name:VerificationCode*@author:terwer*@date:2022-07-1722:21**/publicclassVerificationCode{privatesta......