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

Question

我正在研究来自 this geeksforgeeks article 的 Kruskal 的 MST .给出的步骤是:

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

2. 选择最小的边。检查它是否与目前形成的生成树形成循环。如果未形成循环，则包含此边。否则，丢弃它。

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

我真的觉得没有必要使用不相交集。为了检查一个循环，我们可以只将顶点存储在一个已访问的数组中，并在选择一条边时将它们标记为真。如果我们找到一条边，其两个顶点都在访问数组中，则循环执行程序，我们将忽略该边。

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

Answer 1

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

A - - B - - C - - D

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

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

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

很高兴您能够探索和插入传统的实现并尝试找到改进它们的方法。如果你这样做，你会学到很多关于这些算法的知识!在这种情况下，碰巧您提出的建议不太行得通，了解它行不通的原因有助于阐明现有方法为何如此。