最小生成树图文讲解

本篇主要图文讲解最小生成树的实现和算法。

一、最小生成树

最小生成树（minimumspanningtree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。

此外还可以用bfs和dfs生成，分别叫bfs生成树和dfs生成树。

例：

二、Prim（普里姆）算法

这里就采用的是邻接矩阵存储的，Prim和最短路中的dijkstra很像，方法：

（1）先建立一个只有一个结点的树，这个结点可以是原图中任意的一个结点。

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

（3）重复步骤（2）直到所有顶点都在树中。

如图：

三、kruskal（克鲁斯卡尔）算法

（1）将边按照边权从小到大排序，并建立一个没有边的图T。

（2）选出一条没有被选过的边权最小的边。

（3）如果这条边两个顶点在T中所在的连通块不相同，那么将它加入图T，相同就跳过。

（4）重复（2）和（3）直到图T连通为止。

其实这里只需要维护连通性，可以不需要真正建立图T，还可以用并查集来维护。

这里用邻接表（不是链表）进行操作：

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：