同步操作将从 程序员充电站/LeetCode-Py 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
在了解「最小生成树」之前,我们需要要先理解 「生成树」的概念。
图的生成树(Spanning Tree):如果无向连通图 G 的一个子图是一棵包含图 G 所有顶点的树,则称该子图为 G 的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。
换句话说,生成树是原图 G 的一个子图,它包含了原图 G 的所有顶点,并且通过选择图中一部分边连接这些顶点,使得子图中没有环。
生成树有以下特点:
如上图所示,左侧图 $G$ 是包含 $v_1…v_6$ 共 $6$ 个顶点 $7$ 条边在内的有权图。右侧是图 $G$ 的两个生成树,两者都包含了 $6$ 个顶点 $5$ 条边。
最小生成树(Minimum Spanning Tree):无向连通图 G 的所有生成树中,边的权值之和最小的生成树,被称为最小生成树。
最小生成树除了包含生成树的特点之外,还具有一个特点。
如上图所示,左侧图 $G$ 是包含 $v_1…v_6$ 共 $6$ 个顶点 $7$ 条边在内的有权图。右侧是图 $G$ 的最小生成树,包含了 $6$ 个顶点 $5$ 条边,并且所有边的权值和最小。
为了找到无向图的最小生成树,常用的算法有「Prim 算法」和「Kruskal 算法」。
这两个算法都可以帮助我们找到图中的最小生成树,以满足连接所有顶点的要求同时使得总权重最小。
Prim 算法的算法思想:每次选择最短边来扩展最小生成树,从而保证生成树的总权重最小。算法通过不断扩展小生成树的顶点集合 $MST$,逐步构建出最小生成树。
Kruskal 算法的算法思想:通过依次选择权重最小的边并判断其两个端点是否连接在同一集合中,从而逐步构建最小生成树。这个过程保证了最终生成的树是无环的,并且总权重最小。
在实际实现中,我们通常使用并查集数据结构来管理顶点的集合信息,以便高效地判断两个顶点是否在同一个集合中,以及合并集合。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。