河小马
kruskal的算法是一种数学模型，用于找到无向加权边图的最小生成森林，这是大多数人会觉得难以理解的一堆词。
由于kruskal的算法是一种非常有用的贪婪算法，我们将尽力解释关于它的一切，以便您可以立即开始使用它！
什么是最小生成森林？
最小生成森林是一种连接点的图，其使用最小的权重占用来连接所有图上的点。最小生成森林将根据权重组织点的连接，删除会导致回路的所有连接，然后连接具有最低边权重总和的连接。
加权图有两种类型。加权顶点图将其权重分配给图的顶点，而加权边图将权重分配给边，即顶点之间的连接。
在使用加权图时，了解哪个部分是加权的很重要，因为顶点加权图和边加权图都被称为“加权图”。
kruskal的算法：它是如何工作的？
可以使用加权边图的简单示例来解释kruskal的算法以及kruskal的算法如何组织图中的数据。
©jingzhengli.com
在解释kruskal的算法时，我们最大的弱点不是不知道如何将kruskal的算法应用于准确制作的图中，而是不知道如何绘制加权边图（因为该团队不是数据科学家之一）。但是我们在查看了许多图后尽了最大努力。
应用kruskal的算法的第一步是去除所有的回路或平行边。现在，在这个应用程序中，即图论中，“平行”边实际上并不是平行的，而是存在于同一两个点之间的边。因此，我们将删除点a上的回路以及c和d之间的连接。
这给我们带来了以下结果：
©jingzhengli.com
现在我们必须为这些点分配权重。这个图实际上是没有意义的，没有与之关联的数据。所以，我们只是为图的边分配了随机的权重，并且编造了一个理由以解释为什么该权重有意义。因此，我们得到了以下图：
©jingzhengli.com
一旦图正确地加权，就是时候将所有点之间的互连线遮黑，并使用kruskal的算法开始分析它们，找出连接所有点的最低权重方式 – 在不生成任何回路的情况下。因此，如果使用铅笔跟随路径，路径不能回到自身。
©jingzhengli.com
我们可以看到的第一个顺序权重是1。由于将该边包含在图中不会创建回路，所以我们可以毫不担心地将其包含进去。
©jingzhengli.com
现在，我们必须处理下一个权重，即2。现在，包括所有具有此权重的三条边将创建一个回路 – 一组所有边以完整循环方式相互连接。因此，我们将放弃看起来最长的一条边（但您可以放弃其中任何一条，因为它们的权重都相同）。
©jingzhengli.com
最后，我们需要移动到下一个权重，3。包括这条边不会产生回路，所以我们会将其包括进来。然而，包括剩下的边中的任何一条都会产生回路。因此，我们不会将它们包括进来，这意味着我们的最小生成森林图已经完整！
©jingzhengli.com
kruskal算法：它有什么用途，何时使用它？
kruskal排序算法通常用于找到两个点之间的最短路径。
因此，虽然我们的例子只是按权重对所有点进行排序，但实际应用kruskal算法往往是为了找到包括所有数据点的两个点之间的最短路径。当使用kruskal算法时，您可能想要找到点d和点a之间的距离。您将得到与我们相同的图形，但是您将为不同的原因解决该图形。
kruskal算法：正确性证明
我们想要警告那些对数学和计算机科学不太感兴趣或不熟悉的人，这一部分可能有点难以理解。虽然数学证明不是技术和数学爱好者的专有知识，但在这些条件下更容易理解。但是我们将尝试用简单的语言来解释。
kruskal算法的证明分为两个部分。首先，我们必须证明kruskal算法实际上产生了一棵生成树。一旦我们证明了kruskal算法产生了一棵生成树图，我们必须证明图的总权重是最小的。
证明kruskal算法产生最小生成树
我们将使用印度科学学院的证明，链接在此处：。数学证明是一个非常特定的领域，普通人没有能力进行证明，也不应该在没有适当教育的情况下尝试进行证明。
印度科学学院的以下证明证明了kruskal算法产生了一棵最小生成树。
定理：kruskal算法可以找到一个最小生成树。
证明：设g = (v, e)是一张带权的连通图。设t是kruskal算法中生成的边集。我们通过数学归纳法证明，对于t中的边的数量，如果t在算法的任一阶段都是有希望的，那么当在kruskal算法中添加一条新边时，它仍然是有希望的。
当算法终止时，会发现t给出了问题的解，因此是一棵最小生成树。
基础：t = $ phi$ 是有希望的，因为带权连通图总是至少有一棵最小生成树。
归纳步骤：设在添加一条新边e = (u, v)之前，t是有希望的。t将g的节点划分为一个或多个连通分量。u和v将位于两个不同的分量中，设u是包含u的分量中的节点集合。
注意u是v的真子集，t是一组有希望的边集，使得t中的边都不离开u（因为边t要么两端都在u内，要么两端都不在u内），e是一个离开u的最小代价边（因为kruskal算法是贪心的，只有在检查比e更短的边之后才选择了e）。
上述三个条件与最小生成树引理完全一致，因此我们可以得出结论，t$ cup$ {e}也是有希望的。当算法停止时，t不仅给出了一棵生成树，而且是一棵最小生成树，因为它是有希望的。
j.b. kruskal. on the shortest spanning subtree of a graph and the traveling salesman problem. proceedings of the american mathematical society, volume 7, pp. 48-50, 1956.
kruskal算法：伪代码
伪代码是一种类似于编程语言风格的简单语言。与使用特定编程语言不同，伪代码旨在适用于所有编程语言，只要您理解将伪代码转化为的编程语言。
kruskal算法的伪代码如下：
算法kruskal(g)如下：
algorithm kruskal(g) is
f:= ∅
for each v ∈ g.v do
make-set(v)
for each (u, v) in g.e ordered by weight(u, v), increasing do
if find-set(u) ≠ find-set(v) then
f:= f ∪ {(u, v)} ∪ {(v, u)}
union(find-set(u), find-set(v))
return f这段代码引入了“森林”(f)作为计算机的边集，并使用不相交集数据结构来确定两个点是否属于同一棵树。
最后的思考
kruskal算法是贪心算法的一个很好的例子，它正是它应该做的，并且效率很高！kruskal算法是生成最小生成树图的一种很好的方法，而且它的代码实现非常简单。
如果您是热爱图论的人，您可以通过简单地翻译伪代码来测试这个算法。如果您热爱数学和图论，请在这里留下评论！
