最小生成树的kruskal算法

‘壹’ kruskal算法Kruskal算法

克鲁斯卡尔算法是一种用于构建最小生成树的常用算法，当处理含有 n 个顶点的连通网 WN=(V,{E}) 时，其步骤如下：

首先，从一个初始状态开始，构建一个仅包含 n 个顶点且边集为空的子图，视每个顶点为独立的树根，形成一个由 n 棵树组成的森林。接着，从所有边 E 中挑选权值最小的边，如果这条边连接的两个顶点在不同的树中，就将其添加到子图中，合并两棵树；若两个顶点已属于同一棵树，则跳过该边，继续寻找下一条权值最小的边。这个过程一直持续到森林中只剩下一棵树，即子图的边数达到 n-1 条，此时的子图即为最小生成树。

举个例子，我们可以这样操作：首先对所有的边按权值排序，如图所示，从AD开始连接，逐步构建。然后在剩下的边中，避免选择已形成连通的边，如BC或EF，尽管它们可能是最短的。最终，通过这种方式选择边，直到所有顶点连通，形成最小生成树。

最后的结构如下图所示，所有顶点已通过边连通，完成了最小生成树的构建。

K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

‘贰’ Kruskal 算法

最小生成树，是在含有n个顶点的连通图中，挑选n-1条边构成的树结构，这棵树的全部边的权重之和最小。

Kruskal算法，专用于生成最小生成树。

它的核心思路是，从权值最小的边开始，依次选取连通图中的边，确保所选边不会形成环路，直至得到n-1条边。

开始时，将所有顶点独立成森林，即每个顶点为一棵树。然后按照边的权重从小到大顺序，将边逐一加入森林中。加入时检查，若加入后不会形成环路，则继续加入。直至森林合并为一棵树，即得到了最小生成树。

图中虽未描绘森林状态，但每条边的加入实际是将森林中的树进行连接。例如，选取权值为7的边时，不选择权值为6的边，原因是避免形成环路。