# Overview

本章就两个能说的，也就是最小生成树（MST）问题的两个解法

MST，说人话就是给一张图 G 不断删除边、删除边，
直到只剩 V-1 条边，且所有点相互联通

# Prim 算法

核心为：选择我们的最近邻居入伙

构建一个我们确定联通的点集 Q
初始时，Q 中只有一个起始顶点，边集合为空。然后在每一步，找到一条连接 Q 内顶点和 Q 外顶点的权值最小的边，将这条边加入到边集合中，并把这条边所连接的点加入 Q 中。不断重复，直到所有顶点都在 Q 中。

# Kruskal 算法

核心为：选择把任意两个孤岛打通的最小边

先将图中所有边按照权值从小到大进行排序
初始时，Q 中只有一个起始顶点，边集合为空。然后在每一步，找到一条连接 Q 内顶点和 Q 外顶点的权值最小的边，将这条边加入到边集合中，并把这条边所连接的点加入 Q 中。不断重复，直到所有顶点都在 Q 中。

初始时，最小生成树的边集合 E 为空。然后从权值最小的边开始，依次检查：如果这条边加入到 E，不会形成回路，就将它加入 E；否则下一个。不断重复，直到 E 能够连接所有顶点