最小生成树思维导图
最小生成树详解
树图思维导图提供 最小生成树 在线思维导图免费制作，点击“编辑”按钮，可对 最小生成树 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：c256ad6fa494aa60a45118fb764f63bd
思维导图大纲
最小生成树（MST）思维导图模板大纲
最小生成树概念
边的权值之和最小的生成树
可能有多个，但是权值之和最小且唯一
一棵树本身就是自己的最小生成树；非连通图只有生成森林
普利姆（Prim）算法
算法思想
从某一个顶点开始，每次将到已建成树中的任意节点的代价最小的结点纳入生成树，直到所有结点都纳入
例题
实现思想
isjoin数组标记各节点是否已加入树
lowcost数组记录各节点加入树的最低代价
每轮循环遍历结点，找lowcost最小且还未加入树的结点，加入后再循环更新未加入的lowcost值
总结
时间复杂度
Prim算法O（|V|^2）
Kruskal算法O（|E|log|E|）
适用
Prim算法适用于边稠密图
Krukal算法适用于边稀疏图
其他最小生成树算法
破圈法：每次去除任意环中权值最大的边，直至无环
注意点
由于Prim和Kruskal算法生成结果不一定唯一，所以留心题目问的是不是全部结果！
邻接矩阵存储，最小生成树一定唯一
当带权连通图中又相同较小权值的几条边形成回路，两个算法可能形成不同的最小生成树
如果各条边权值互不相同，则最小或次小权值的边一定在最小生成树上，第三小不一定，可能形成回路
克鲁斯卡尔（Kruskal）算法
算法思想
每次选择一条权值最小的边，使这条边两头连通，已连通则不选这条边
例
算法实现
将各边按权值排序
检查每条边的两个顶点，判断是否属于同一个集合
相关思维导图模板
树图思维导图提供 苹果树冠问题思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 苹果树冠问题思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：081917a9f5beb360eaf940f57aa8fd6a
树图思维导图提供 数据处理流程 在线思维导图免费制作，点击“编辑”按钮，可对 数据处理流程 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：eda5b2f19ebaa0f6539dbe191ab33bf8
沪公网安备 31011502019485号
上海工商