1 最小生成树

1.1 生成树

无向图 $G$ 的生成树，就是具有图 $G$ 的所有顶点，但是边数最小的联通子图

更加详细的定义: Wikipedia – 生成树

1.2 最小生成树

带权联通无向图的总权值最小的生成树

更加详细的定义: Wikipedia – 最小生成树

1.3 求解算法

• Kruskal 算法
• Prim 算法

Continue reading “Kruskal 最小/大生成树 — Luogu P1967 货车运输”