prim和kruskal算法

Prim算法和Kruskal算法都是用于求解最小生成树（Minimum Spanning Tree, MST）问题的经典贪心算法。最小生成树问题是图论中的一个重要问题，旨在在一个带权无向连通图中找到一棵生成树，使得这棵生成树的边权之和最小。

### Prim算法
Prim算法是一种贪心算法，从一个初始顶点开始，逐步扩展生成树，直到包含图中的所有顶点。其基本步骤如下：
1. 选择一个起始顶点，将其加入生成树。
2. 从生成树中的顶点出发，选择一条权重最小的边，将其连接的顶点加入生成树。
3. 重复步骤2，直到所有顶点都被包含在生成树中。

**优点：**
- 对于稠密图（边数接近顶点数的平方），Prim算法的时间复杂度较低。

**缺点：**
- 需要维护一个优先队列来选择权重最小的边，时间复杂度较高。

### Kruskal算法
Kruskal算法也是一种贪心算法，通过不断选择权重最小的边来构建生成树。其基本步骤如下：
1. 将图中的所有边按权重从小到大排序。
2. 从权重最小的边开始，依次选择边，如果加入这条边不会形成环，则将其加入生成树。
3. 重复步骤2，直到生成树包含n-1条边（n为顶点数）。

**优点：**
- 对于稀疏图（边数远小于顶点数的平方），Kruskal算法的时间复杂度较低。

**缺点：**
- 需要使用并查集（Union-Find）来检测环，时间复杂度较高。

### 对比
- **适用场景：** Prim算法适用于稠密图，Kruskal算法适用于稀疏图。
- **时间复杂度：** Prim算法的时间复杂度为O(V^2)，Kruskal算法的时间复杂度为O(E log E)，其中V为顶点数，E为边数。

### 示例
假设我们有一个带权无向连通图，Prim算法和Kruskal算法都能找到该图的最小生成树。

图示：
  A
 / \
1   3
 /     \
B-------C
 \     /
  1   1
   \ /
    D

最小生成树：
  A
 / \
1   3
 /     \
B       C
 \
  1
   \
    D