graph-最小生成树

本文最后更新于：2022年5月28日 凌晨

摘要：

最小生成树

连接图G的所有顶点构成的边构成的树，且其总权重最下

  • 包含图中全部的n个顶点，边的条数为n-1
  • 所欲生成树中总权值最下

Prim算法

切分定理

  • 切分（Cut）：把图中的节点分为两部分，称为一个切分

  • 横切变（Crossing Edge）：如果一个边的两个顶点，分别属于切分的两部分，这个边称为横切边

切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树

数据结构 > 图 算法 > 图
#数据结构 #图 #prim #kruskal
graph-最小生成树
https://shgang97.github.io/posts/graph-minimum-spanning-tree-c75337d77627/
作者
shgang
发布于
2022年5月20日
更新于
2022年5月28日
许可协议