克鲁斯卡尔算法可以用这种方式实现，而不是使用不相交集森林吗？

Question

我正在从geeksforgeeks 文章中研究 Kruskal 的 MST 。给出的步骤是：

\n\n

\n

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

\n

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

\n

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

\n

\n\n

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

\n\n

换句话说，我们可以\xe2\x80\x99t而不是存储不相交集的森林，而只存储一个位数组来指示哪些顶点在先前的步骤中已链接到另一条边？

\n

Answer 1

您\xe2\x80\x99 描述的方法并非在所有情况下都能正常工作。作为示例，请考虑以下折线图：

\n\n

A - - B - - C - - D\n

\n\n

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

\n\n

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

\n\n

这里的问题是，在构建 MST 时，您可能会添加连接过去已经链接到其他节点的节点的边。因此，添加边的标准是少 \xe2\x80\x9chave 这些节点之前已链接过？\xe2\x80\x9d 和更多 \xe2\x80\x9cis 这些节点之间已经有一条路径？\xe2\x80\x9d \xe2\x80\x99s 是不相交集森林出现的地方。

\n\n

\xe2\x80\x99 很高兴你\xe2\x80\x99 不断探索传统的实现并试图找到改进它们的方法。如果你这样做的话，你\xe2\x80\x99将会学到很多关于这些算法的知识！在这种情况下，碰巧你所提议的方法并不能很好地工作，而了解为什么它不能工作有助于阐明为什么现有的方法是什么这是。

\n