今天做洛谷的时候刷到好多图论的题，发现自己在这一方面算法的掌握还是有待提高啊。在这就先介绍最小生成树的算法吧。

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。 最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。 此外还可以用bfs和dfs生成，分别叫bfs生成树和dfs生成树。 例：

这里就采用的是邻接矩阵存储的， 个人觉得Prim和最短路中的dijkstra很像，方法： ① 先建立一个只有一个结点的树，这个结点可以是原图中任 意的一个结点。

② 使用一条边扩展这个树，要求这条边一个顶点在树中另一 个顶点不在树中，并且这条边的权值要求最小。

③ 重复步骤②直到所有顶点都在树中。 如图：