一、生成树与最小生成树的区别

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

生成树：一个连通图的生成树是一个极小的连通子图，它包含图中全部的顶点，但是只有足以构成一棵树的n-1条边

最小生成树：我们把构造带权连通无向图的最小代价生成树称为最小生成树（一颗生成树的代价就是树上各边的代价之和）

二、Prim算法

2.1算法思想

1. 假设从以下图中挑选一个点，从v0开始，我们需要两个数组

   1. 第一个数组标记：顶点是否有被加入到我们正在组建的最小生成树中，一开始只选择了v0，因此在v0处打勾，其他打叉
   2. 第二个数组表明了，此时把各结点加入到生成树中需要花费的代价
   3. 若把v1加入到树中，需要6，v2加入需要5这么多，v4或v5是v0没有直接相连的边，因此目前我们暂时无法将它们两放入到树中，因此用∞来标记
      

2. 进行第一轮处理，我们遍历所有结点，找出lowcast最低的，且没有加入到树的结点，

   1. 因此我们选择的是v3，在isjoin打勾
   2. 再次便利循环，我们还没有加入的各个顶点lowcast
   3. 由于最开始v0连接v1的lowcast为6，但是此时加入了v3，我们可以从直接从v3-v1 = 5
   4. v2也是如此，v3-v2 = 4
   5. v4、v5也是如此更新
      

3.第二轮的处理与第一轮的处理类似的…

1. 我们从左往右挑选，lowcast最小且未被访问过为v2，那么我们讲v2加入到树中…

4.循环结束，以下为遍历结果

三、Kruskal算法

1. 需要找到权值最小的边，我们首先将各边按权值递增排序，值最小的边是连接v0、v3，检查边的两个顶点是否连通，若原本不连通，原本属于不同的集合，那么我们就将其选上，因此v0和v3变成同一个集合
2. v2和v5值最小，且不本不连通，那么我们将其连接起来，变成同一个集合
3. 以此类推
4. v3、v5已经从属同一个集合了，因此我们跳过
   

四、时间复杂度

使用并查集来判断是否同属于一个集合

五、主要知识点回顾