图论之最小生成树

定义

在连通的带权图的所有生成树中，权值和最小的那颗生成树（包含图中所有顶点的树），称为最小生成树。

针对问题：带权图的最短路径问题。

解法

普里姆（Prim）算法

以 点 为基础，挑选与 已有点 相连的最小边。

克鲁斯卡尔（Kruskal）算法——常用

是以 边 为基础，先将边从小到大排列，从小到大的添加不构成「环路」的边。

判断「环路」使用的是 并查集 的数据结构 学习并查集