java - 找到连接图的最低成本的替代方法

Question

我遇到了一个经典的 Kruskals 问题，在这个问题中，给定一个无向图和边之间的一组权重，要求我找出连接边所需的最小成本。我对 Kruskals 算法不太熟悉，所以我想出了自己的解决方案。但是，它在一些测试用例上表现不佳。这是算法: 1-根据权重对边缘进行排序。使用了 Node 类型的优先级队列。Node 由 src、dest 和 weight 组成。

2- 使用大小为 N 的 boolean 数组跟踪访问过的节点，其中 N 是节点数。

2-轮询优先级队列(移除头部)。如果未访问 src 或 dest，则将权重添加到解决方案，并将它们都标记为已访问。

有人可以帮我解决这个算法为什么会出现问题吗？从逻辑上讲，在我看来，访问过的数组应该跟踪以确保没有循环，因为如果 src 或 dest 未被访问，我只会将它添加到解决方案中。

Answer 1

在某些时候，您通常需要在两个端点都被访问的解决方案中添加一条边。例如，考虑下图:

A --1-- B
|
|
3
|
|
C --2-- D

在解决方案中添加边 AB 和 CD 后，您的算法将拒绝添加 AC，因为 A 和 C 都已被访问。

如果端点已经在同一棵树中，则 Kruskal 算法拒绝向解决方案添加边，这与您的情况非常不同。