最小生成树笔记（Prim算法Kruskal算法）

1.最小生成树

最小生成树（Minimum Spanning Tree，简称MST）是指：在一个连通无向图中，找到一个包含所有顶点的树，且该树的所有边的权重之和最小。

换句话说，最小生成树是原图中的一个子图，它包含所有顶点，并且连接所有顶点的边的权重之和最小。

---

最小生成树的定义有以下特点：

1. 最小生成树是无向图的一种树形结构，其中没有环（即没有闭合路径）。
2. 最小生成树包含图中的所有顶点，但只包含足够数量的边来连接这些顶点，使得树成为一个连通的图。
3. 最小生成树的总权重（边的权重之和）应该最小，即从所有可能的生成树中选择边权重之和最小的树。

最小生成树算法的目标是找到满足上述条件的最优解，常用的算法包括Prim算法和Kruskal算法。这些算法可以在连通无向图中找到最小生成树，并且在不同应用中具有重要的应用价值，如网络设计、电路布线、城市规划等。

---

2.Prim算法

Prim算法是一种用于求解最小生成树的贪心算法。

它从图的某个顶点开始，逐步将距离当前生成树最近的顶点加入生成树，直到所有顶点都被包含在最小生成树中。

Prim算法的基本思想是通过不断地选择与当前生成树最近的顶点，并将该顶点与生成树中的一个顶点连接，来逐步构造最小生成树。

Prim算法的步骤如下：

1. 选择一个起始顶点作为初始生成树，将该顶点加入生成树中。
2. 初始化一个辅助数据结构（如优先队列或最小堆），用于存储与当前生成树相连的边，并按边的权重值排序。
3. 在辅助数据结构中选择权重最小的边（即与当前生成树最近的边），将其相连的顶点加入生成树，并将该边从辅助数据结构中移除。
4. 重复步骤3，直到所有顶点都被包含在生成树中。

Prim算法的过程可以保证生成的树是连通的，并且是最小生成树。它的时间复杂度取决于辅助数据结构的实现方式，一般情况下为O(ElogV)，其中E是图的边数，V是图的顶点数。

---

3.Kruskal算法

Kruskal算法也是一种用于求解最小生成树的贪心算法。

它与Prim算法类似，但在选择边的方式上略有不同。Kruskal算法是基于边来构建最小生成树的，而不是基于顶点。

Kruskal算法的基本思想是从图的边集合中选择权重最小的边，并将其加入生成树中，直到生成树中包含了所有的顶点为止。

在选择边的过程中，需要保证生成树不形成环路，因此可以使用并查集来辅助判断两个顶点是否处于同一个连通分量。

Kruskal算法的步骤如下：

1. 将图的所有边按照权重值从小到大排序。
2. 初始化一个并查集，用于判断顶点之间的连通性。
3. 依次遍历排序后的边集合，如果当前边的两个顶点不在同一个连通分量中，就将该边加入生成树，并合并两个顶点所在的连通分量。
4. 重复步骤3，直到生成树包含了所有顶点。

Kruskal算法的过程可以保证生成的树是连通的，并且是最小生成树。它的时间复杂度取决于边排序和并查集操作的复杂度，一般情况下为O(ElogE + ElogV)，其中E是图的边数，V是图的顶点数。