带你读《图解算法小抄》二十五、图（6）

带你读《图解算法小抄》二十五、图（5）https://developer.aliyun.com/article/1347768?groupCode=tech_library

7.克鲁斯卡尔算法

克鲁斯卡尔算法是一种最小生成树算法，它找到连接森林中的任意两棵树的权重最小的边。它是一种贪心算法，在图论中用于在连通的带权图中添加成本递增的边来找到最小生成树。这意味着它找到一组边，形成一个包含每个顶点的树，使得树中所有边的权重之和最小。如果图不连通，则它找到一个最小生成森林（每个连通分量的最小生成树）。

Kruskal Algorithm

Kruskal Demo

基于欧几里德距离的克鲁斯卡尔算法演示。

1）最小生成树

最小生成树（MST）或最小权重生成树是连接所有顶点的边的子集，没有任何环且具有最小可能的总边权重的连通带权（非）有向图。也就是说，它是一个生成树，其边权重之和尽可能小。更一般地，任何带权无向图（不一定是连通的）都有一个最小生成森林，即其连通分量的最小生成树的并集。

带你读《图解算法小抄》二十五、图（7）https://developer.aliyun.com/article/1347766?groupCode=tech_library