### **Prim算法**

#### **时间复杂度**
Prim算法的时间复杂度取决于图的存储方式和优先队列的使用：  

1. **邻接矩阵表示**：  
   - 每次选择最小权值的边需要遍历所有顶点，时间复杂度为 \( O(V^2) \)。  
   - 适合**稠密图**（边较多时，通常 \( E \approx V^2 \)）。

2. **邻接表表示 + 最小堆**：  
   - 初始化堆时，将所有边加入堆的时间复杂度为 \( O(V \log V) \)。  
   - 在堆中插入或删除边的操作为 \( O(\log V) \)，遍历所有边需要 \( O(E \log V) \)。  
   - 总复杂度为 \( O(E \log V) \)，适合**稀疏图**（边较少时，通常 \( E \ll V^2 \)）。

#### **空间复杂度**
- **邻接矩阵表示**：\( O(V^2) \) 用于存储所有顶点间的权值信息。  
- **邻接表表示 + 最小堆**：  
  - 邻接表占用 \( O(V + E) \)。  
  - 优先队列（最小堆）需要 \( O(V) \) 的空间。  
  - 总空间复杂度为 \( O(V + E) \)。  

---

### **Kruskal算法**

#### **时间复杂度**
Kruskal算法的时间复杂度主要由以下部分组成：  

1. **边排序**：  
   - 使用快速排序或堆排序对 \( E \) 条边排序，时间复杂度为 \( O(E \log E) \)。  
2. **并查集操作**：  
   - 查找和合并操作的时间复杂度为 \( O(\alpha(V)) \)（近似常数），每条边最多进行一次，整体为 \( O(E \cdot \alpha(V)) \)。  
   - 其中 \( \alpha(V) \) 是反Ackermann函数，增长极慢，可认为是一个很小的常数。

总时间复杂度：  
- \( O(E \log E + E \cdot \alpha(V)) \)。  
- 由于 \( E \log E \geq E \cdot \alpha(V) \)，最终复杂度可以简化为 \( O(E \log E) \)。  

#### **空间复杂度**
- 用于存储所有边的列表：\( O(E) \)。  
- 并查集数组（parent 和 rank）：\( O(V) \)。  
- 总空间复杂度为 \( O(E + V) \)。  

---

### **时间和空间复杂度对比**

| **算法**       | **时间复杂度**               | **空间复杂度**         | **适用场景**              |
|-----------------|------------------------------|-------------------------|---------------------------|
| **Prim 算法**  | \( O(V^2) \) 或 \( O(E \log V) \) | \( O(V^2) \) 或 \( O(V + E) \) | 稠密图/稀疏图             |
| **Kruskal 算法**| \( O(E \log E) \)            | \( O(E + V) \)          | 较稀疏的图                |  

**总结**：  
- **稠密图**（\( E \approx V^2 \)）：Prim 算法使用邻接矩阵效果更好。  
- **稀疏图**（\( E \ll V^2 \)）：Kruskal 算法效率更高，且更易实现。