时间戳

首页 > 解决方案 > Kruskal 的算法能否以这种方式实现而不是使用不相交集森林？

algorithm - Kruskal 的算法能否以这种方式实现而不是使用不相交集森林？

问题描述

我正在从这篇 geeksforgeeks 文章中学习 Kruskal 的 MST 。给出的步骤是：

  1. 按权重的非递减顺序对所有边进行排序。

  2. 选择最小的边。检查它是否与到目前为止形成的生成树形成一个循环。如果没有形成循环，则包括该边。否则，丢弃它。

  3. 重复步骤（2）直到生成树中有（V-1）条边。

我真的觉得没有必要使用不相交集。代替检查循环，我们可以将顶点存储在访问数组中，并在选择边缘时将它们标记为真。如果我们发现一条边的两个顶点都在访问的数组中，则循环通过程序，我们将忽略该边。

换句话说，我们不能只存储一个位数组，而不是存储一个不相交的森林，而是存储一个位数组，指示哪些顶点在之前的某个步骤中已链接到另一条边？

标签： algorithmminimum-spanning-treekruskals-algorithm

解决方案

您描述的方法并非在所有情况下都能正常工作。例如，考虑这个折线图：

A - - B - - C - - D

假设 AB 的权重为 1，CD 的权重为 2，B - C 的权重为 3。Kruskal 的算法在这里会做什么？首先，它会添加 A - B，然后是 C - D，然后是 B - C。

现在想象一下你的实现会做什么。当我们添加 A - B 时，您会将 A 和 B 标记为已访问。然后当我们添加 C - D 时，您会将 C 和 D 标记为已访问。但是当我们尝试添加 B - C 时，由于 B 和 C 都被访问，您将决定不添加边，从而留下未连接的结果。

这里的问题是，在构建 MST 时，您可能会添加连接过去已经链接到其他节点的节点的边。因此，添加边的标准更少“这些节点以前是否链接过？” 以及更多“这些节点之间是否已经存在路径？” 这就是不相交的森林进来的地方。

很高兴您正在探索和推动传统的实现，并试图找到改进它们的方法。如果你这样做，你会学到很多关于这些算法的知识！在这种情况下，碰巧你提出的建议并不完全奏效，而了解它为什么不起作用有助于阐明为什么现有方法是这样的。

推荐阅读