最小生成树怎么求

最小生成树是指在一张无向加权图中找到一棵生成树，使得生成树边权之和最小。求最小生成树的经典算法是Prim算法和Kruskal算法。

1. Prim算法

Prim算法的思路是从一个顶点开始，选择与该顶点相邻且权值最小的边，将该边的另一个顶点加入生成树的顶点集合中，以此类推，直到所有顶点都在生成树中。

具体步骤如下：

（1）从任意一个顶点开始，将该顶点加入生成树的顶点集合中。

（2）将该顶点与生成树中其它顶点相邻的边加入优先队列中。

（3）从优先队列中选择权值最小的边，判断其另一个顶点是否已经在生成树中。

（4）如果已经在生成树中，则选择下一条边；否则，将该边的另一个顶点加入生成树的顶点集合中，并将该顶点与生成树中其它顶点相邻的边加入优先队列中。

（5）重复步骤（3）和（4），直到生成树包含所有顶点为止。

2. Kruskal算法

Kruskal算法的思路是将所有边按权值从小到大排序，然后依次将权值最小的边加入生成树，加入时判断是否构成环，如果不构成环，则加入该边。

具体步骤如下：

（1）将所有边按权值从小到大排序。

（2）从权值最小的边开始，依次加入生成树，判断边的两个端点是否在同一个连通分量中。

（3）如果不在同一个连通分量中，则将这两个端点合并成一个连通分量，并将这条边加入生成树中。

（4）重复步骤（2）和（3），直到生成树包含所有顶点为止。