Kruskal 算法

Kruskal 算法用于找到生成树的最小成本。 生成树是使用所有顶点连接的图，其中没有循环。 换句话说，我们可以说从任何顶点到任何其他顶点都有一条路径，但没有循环。

什么是最小成本生成树？

最小生成树是具有最小总边权重的生成树。 Kruskal 算法是一种以图为输入并从图中找到构成包含图的每个顶点的树的边的算法。

Kruskal 算法的工作原理

Kruskal 算法的工作从具有最低权重的边开始，并不断添加边，直到我们达到目标。

以下是用于实现 Kruskal 算法的步骤

• 首先，按其边权重的升序对边进行排序。
• 考虑具有最低权重的边，并将其添加到生成树中。 如果在生成树中添加任何边会创建一个循环，则拒绝该边。
• 继续添加边，直到我们到达结束顶点。

让我们通过一个例子来理解。

考虑下图。

现在我们必须计算上述图的最小生成树。 为了找到最小成本生成树，第一步是从图中删除所有循环和平行边。 在这里，平行边是指两个顶点之间存在多条边。 例如，在上图中，顶点 A 和 B 之间存在两条边，其权重分别为 5 和 10，因此这些边是平行边。 我们必须删除任何一条边。

如果存在平行边，则将删除权重最高的边。 在上图中，如果我们考虑顶点 A 和 B，则权重为 10 的边大于权重为 5 的边，因此我们丢弃权重为 10 的边。 因此，我们删除权重为 10 的边，如下所示

删除平行边后，我们将根据其边权重的递增顺序排列边。 正如我们在上图中观察到的，最小边是 2。 有两条边的权重等于 2，可以写成

BD = 2

DE = 2

下一个最小边权重是 3。 有两条边的权重为 3，因此可以写成

AC = 3

CD = 3

下一个具有最小权重的边是 4。 只有一条边的权重为 4，可以写成

BE = 4

下一个具有最小权重的边是 5。 只有一条边的权重为 5，可以写成

AB = 5

下一个具有最小权重的边是 6。 只有一条边的权重为 6，可以写成

CB = 6

下一个具有最小权重的边是 7。 只有一条边的权重为 7，可以写成

AF = 6

下一个具有最小权重的边是 8。 只有一条边的权重为 8，可以写成

FC = 6

边权重以递增顺序写好后，第三步是根据其权重连接顶点。 边权重 2 是最小的，因此我们连接具有边权重 2 的顶点，如下所示

下一条边是 AC，权重为 3，如下所示

下一条边是 CD。 如果我们连接顶点 C 和 D，则它不会形成任何循环，如下所示

下一条边是 BE。 但我们不能连接顶点 B 和 E，因为它会形成一个循环。

下一条边是 AB。 但我们不能连接顶点 A 和 B，因为它会形成一个循环。

下一条边是 BC。 但我们不能连接顶点 B 和 C，因为它会形成一个循环。

下一条边是 AF。 如果我们连接顶点 A 和 F，则它不会形成任何循环，如下所示

算法

用 C++ 实现 Kruskal 算法

输出