生成树 Kruskal 算法
克鲁斯卡尔算法（Kruskal）找到最小成本生成树的算法使用贪婪方法。该算法将图形视为森林，并将其具有的每个节点视为单独的树。一棵树只有在所有可用选项中成本最低且不违反MST属性的情况下，才与另一棵树连接。要了解Kruskal的算法，让我们考虑以下示例-
第1步-删除所有循环和平行边
如果边缘平行，则保持成本最低的边缘，并去除所有其他边缘。
第2步-按权重增加的顺序排列所有边缘
下一步是创建一组边缘和权重，并按重量（成本）的升序排列它们。
步骤3-添加重量最小的边缘
现在，我们开始从权重最小的边开始向图添加边。在整个过程中，我们将继续检查跨接属性是否保持完整。如果通过添加一条边，生成树属性不成立，那么我们将考虑在图中不包括边。
最小的成本是2，涉及的边是B，D和D，T。我们添加它们。添加它们不会违反生成树属性，因此我们继续进行下一个边缘选择。下一个成本是3，且关联的边是A，C和C，D。我们再次添加它们-
表中的下一个成本是4，我们观察到将其相加会在图中创建一个线路。-
我们忽略它。在此过程中，我们将忽略/避免产生电路的所有边缘。
我们观察到成本为5和6的边也会产生电路。我们忽略它们，继续前进。
现在我们只剩下一个要添加的节点。在可用的两个成本最低的边之间7和8，我们将边加上成本7。
通过添加边S，A，我们包括了图的所有节点，现在我们有了最小成本生成树。
第1步-删除所有循环和平行边
如果边缘平行，则保持成本最低的边缘，并去除所有其他边缘。
第2步-按权重增加的顺序排列所有边缘下一步是创建一组边缘和权重，并按重量（成本）的升序排列它们。
步骤3-添加重量最小的边缘现在，我们开始从权重最小的边开始向图添加边。在整个过程中，我们将继续检查跨接属性是否保持完整。如果通过添加一条边，生成树属性不成立，那么我们将考虑在图中不包括边。
最小的成本是2，涉及的边是B，D和D，T。我们添加它们。添加它们不会违反生成树属性，因此我们继续进行下一个边缘选择。下一个成本是3，且关联的边是A，C和C，D。我们再次添加它们-
表中的下一个成本是4，我们观察到将其相加会在图中创建一个线路。-
我们忽略它。在此过程中，我们将忽略/避免产生电路的所有边缘。
我们观察到成本为5和6的边也会产生电路。我们忽略它们，继续前进。
现在我们只剩下一个要添加的节点。在可用的两个成本最低的边之间7和8，我们将边加上成本7。
通过添加边S，A，我们包括了图的所有节点，现在我们有了最小成本生成树。