Kruskal的算法(Kruskal's Algorithm)
Kruskal用于查找最小成本生成树的算法使用贪婪方法。 此算法将图形视为森林，将每个节点视为单个树。 树仅连接到另一个树，并且仅当它在所有可用选项中具有最低成本且不违反MST属性时。
要了解Kruskal的算法，让我们考虑以下示例 -
步骤1 - 删除所有循环和平行边缘
从给定图中删除所有循环和平行边。
如果是平行边缘，请保留成本最低的一个并删除所有其他边缘。
步骤2 - 按重量增加的顺序排列所有边缘
下一步是创建一组边和重量，并按重量（成本）的升序排列。
步骤3 - 添加权重最小的边缘
现在我们开始从具有最小权重的图形开始向图形添加边缘。 在整个过程中，我们将继续检查跨越属性是否完好无损。 如果通过添加一条边，生成树属性不成立，那么我们将考虑不在图中包含边。
最低成本是2，涉及的边是B，D和D，T。 我们添加它们。 添加它们不会违反生成树属性，因此我们继续进行下一个边缘选择。
下一个成本是3，相关的边是A，C和C，D。 我们再次添加它们 -
表中的下一个成本是4，我们观察到添加它将在图中创建一个电路。 -
我们忽略它。 在此过程中，我们将忽略/避免创建电路的所有边缘。
我们观察到成本为5和6的边缘也会产生电路。 我们忽略它们并继续前进。
现在我们只剩下一个要添加的节点。 在可用的最小成本边缘7和8之间，我们将添加成本为7的边缘。
通过添加边S，A，我们已经包含了图的所有节点，现在我们有了最小的成本生成树。
