python 求最小生成树

在Python中，求最小生成树可以使用Prim算法或者Kruskal算法来实现。下面是两种算法的简要介绍：

1. Prim算法：
- Prim算法是一种贪心算法，用于求解加权无向连通图的最小生成树。
- 算法步骤：
1. 选择一个起始顶点，将其加入最小生成树的集合。
2. 从已选择的顶点集合中，选择一条边连接到未选择的顶点，并且该边的权值最小。
3. 将该边连接的未选择顶点加入最小生成树的集合。
4. 重复步骤2和步骤3，直到所有顶点都被选择。
- Python中可以使用Prim算法的库函数networkx来实现，具体可以参考networkx官方文档。

2. Kruskal算法：
- Kruskal算法也是一种贪心算法，用于求解加权无向连通图的最小生成树。
- 算法步骤：
1. 将图中的所有边按照权值从小到大进行排序。
2. 依次选择权值最小的边，如果该边连接的两个顶点不在同一个连通分量中，则将该边加入最小生成树的集合，并将这两个顶点合并到同一个连通分量中。
3. 重复步骤2，直到最小生成树的边数等于顶点数减一。
- Python中可以使用Kruskal算法的库函数networkx来实现，具体可以参考networkx官方文档。