最小生成树涉及知识点

最小生成树（Minimum Spanning Tree, MST）是图论中的一个重要概念，主要用于解决网络设计、电路布局、城市规划等领域的优化问题。以下是涉及的一些知识点：

1. **图的基本概念**：包括有向图、无向图、边的权重（代表成本或距离）、顶点（节点）等。

2. **图的表示法**：邻接矩阵和邻接表是常见的图数据结构，这里使用了邻接矩阵来存储图的结构，便于计算边的连接情况。

3. **算法思想**：
- **Prim算法**：从任意一个顶点开始，逐步添加与现有树相连的最短边，直到添加完整个树，保证了每个新加入的边都是当前树中到其余顶点的最短路径。
- **Kruskal算法**：按边的权重从小到大排序，依次选取边，只要这条边不会形成环，就将其添加到树中，直到树包含所有顶点。

4. **贪心策略**：这两种算法都采用贪心策略，即在每一步选择局部最优解，期望最终能得到全局最优的结果。

5. ** Kruskal 的关键操作**：如`FindKruskal` 中的并查集（union-find），用于判断新加入的边是否形成了环。

6. **权值最小化**：最小生成树的目标是最小化边的总权重，也就是找到一棵连通图，使得所有顶点之间的边的总长度最短。

7. **应用场景**：例如无线通信网络的设计、路由算法、电力网布线等，需要找到一个连通的子图，使得整体成本最低。

8. **复杂度分析**：Prim通常使用优先队列实现，时间复杂度为O(E log V)，其中E是边的数量，V是顶点数量；Kruskal则为O(E log E)，因为需要对所有边进行排序。