此处主要记录最小生成树的个人理解，目标是为了个人复习，而不是为了讲清楚

一张图的树可以有很多种，找到权重和最小的那棵树

Prim 算法

前置工作：得到邻接矩阵

输入部分可能要想一想怎么构建出邻接矩阵

邻接矩阵的值：

• 0：表示自己（后面也顺便成了访问过的标记）
• INF：表示不直接相连
• 正整数：表示权重（距离）

假设从v0节点开始，先取出邻接矩阵的该行，表示的是到其它各个节点的距离（也包括了自己）

现在有两个数组，一个用于记录到其它节点的距离（权重），另一个表示是从哪个节点看过去的，刚开始都是从v0出发来看的，因此初始化为0，即v0的id

遍历剩余的节点

找到距离最近的那个（擂台法）（0距离的不参与）

记录这个节点的id

从这个节点出发看其它节点的距离，与原来数组的值比较，取最小的，如果从这个节点更近，则需要修改出发节点为该节点id（主要是为了输出）

这样距离数组就是这个节点和初始节点（前面的节点）作为一个整体到其它节点的距离了

为了避免重复，要把以及访问过的节点在距离数组中都改为0，这样就不会把访问过的也拿进去参与比较

这样直至整个距离数组都是0了

注意，起始节点可以是任意一个

与Dijkstra的区别是这个是找相对于这个整体最近的，而Dijkstra永远是找从起始节点出发最短的路，比较的是直接到达和简介抵达哪个最短

Kruskal 算法

与上一个不同，这个要构建边集

边集数组记录改边连通的起始节点和终止节点，以及距离

思想就是：首先进行排序，依次取出最小的边，跳过会让图形成回路的边就完事了

主要是如何判断已经形成了回路

定义一个终点节点数组，记录每个节点的最小生成树的终止节点

刚开始都初始化为0

考虑如果放入一条边：查找这条边的起始节点和终止节点

如果该节点在终止数组里面不为0，就顺着找下去，直到为0，这个过程相当于是在沿着节点所在的树走直到走到终点，那么如果放入这点边，我应该把这个终点和终止节点的终点连上，让它合并为一棵树

如果它们找到了相同的终点，则说明已经在同一颗树里面，连上则会形成回路，因此不能要