package
0.0.0-20240627085529-3c531c578999
Repository: https://github.com/ct-zh/golearn.git
Documentation: pkg.go.dev
# README
最小生成树
最小生成树(Minimum Spanning Tree, MST), 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点， 并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
简化版： 只针对带权图连通图,存在一棵树,连接了图里的所有节点,所有边的权值相加是最小的
Prim算法
- 切分 cut: 把图的所有结点分为两个部分，称为一个切分
- 横切边 Crossing Edge: 如果一个边的两个端点，属于切分不同的两边，这个边称为横切边 Crossing Edge
- 切分定理 cut property: 给定任意的切分，横切边中权值最小的边必然属于最小生成树
lazy prim
lazy prim需要用到最小堆结构，见最小堆
代码见lazyPrimMST
prim
kruskal算法
# Functions
创建一个空的最小索引堆 capacity: 最小索引堆的容量.
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
# Structs
lazy prim 流程 把节点0作为切分的一部分，剩下的节点作为切分的另外一部分， 这样节点0的所有边都是横切边 将所有边写入最小堆中（lazy的原因：写入堆中的是所有边，而不是横切边。 因为后面可能出现情况：如节点0，1，2作为一个切分(横切边[0,1],[0,2])，最小堆中写入了边[1,2]， 这个边不是横切边，不应该加入堆中，但是lazyPrim则忽略了这点） 最小堆的顶点是这些边中权值最小的边，根据切分定理，此边必然属于最小生成树 假设从最小堆里取出的是[0,7]这条边，那么将节点7也划分到切分中 这样节点7对应的边也将压入堆中，再从最小堆中取出权值最小的边.
prim 流程： 设置一个最小索引堆 把节点0作为切分的一部分，剩下的节点作为切分的另外一部分， 将节点0的所有横切边的另一个顶点与对应的权值写入最小索引堆 获取到最小索引堆里的最小值，将其对应的顶点加入切分，例如这里是节点7 同样的，将节点7对应的横切边里另外一个顶点与对应的权值写入最小索引堆 *注意，这里如果遇到已经在堆的顶点，例如顶点6,存在[0,6],[6,7]两条横切边 如果[6,7]这条边权值小于[0,6]，则更新掉索引堆里6对应的权值 以上操作重复循环，直到所有点都划入新的切分中，即可得到最小生成树.