最小生成树算法

在了解最小生成树之前，我们需要了解什么是连通图

所谓连通图，即任意一个顶点都与另外任意一个顶点连通的图

生成树即在遍历连通图时所走过的顶点及边的连通子图

最小生成树即对于有权值边的图中，边的权值之和最小的生成树

最小生成树算法：Kruskal算法和Prim算法

Kruskal算法

将连通图的边按从小到大的顺序依次排列，并从小到大遍历边，若将该条边添加到生成树后不构成回环，则将该条边加入树。

构成回环的条件：该条边的两个端点的终点都不想用即不构成回环，反之则构成回环。

终点：与该顶点连接的索引最大的顶点即为终点，若该顶点不与任何顶点连接（即初始状态），则该顶点的终点为其本身。

Prim算法

将连通图的顶点分为两类，一类为已添加的顶点（称为a类），另一类为除已添加的顶点之外的顶点（称为b类）。

先将任意一点加入a类，然后循环遍历a类顶点的边，将与已连接a类顶点且其另一顶点不与a类权值最小的边添加到生成树中，直到b类中无顶点为止，最后所得的即为最小生成树。