algorithm - 在 Prim 算法中卡住并用完节点？

Question

所以我有这张图

我正在尝试构建它的最小生成树。从顶点 AI 开始走 ABFED 之后就无处可去，考虑到 D 的所有相邻顶点都已经是树的一部分，我该如何继续？

另外，如何计算新边的值范围以成为最小生成树的一部分？

提前谢谢各位。

Answer 1

我认为您对 Prim 算法的工作原理略有误解。根据您上面给出的描述，您似乎认为 Prim 的算法是这样工作的：

• 从任何节点开始。
• 查看连接到您尚未访问的当前节点的所有节点。
• 转到这些节点中最便宜的。
• 重复直到覆盖所有节点。

这与 Prim 算法的工作原理很接近，但并不完全正确。在 Prim 的算法中，没有“当前”节点的概念。相反，您有两组节点：已添加的节点和未添加的节点。Prim 算法的工作原理如下：

• 从任何节点开始。将其添加到“in”集中。
• 查看所有连接到“in”集合但尚未添加到“in”集合的节点。
• 将这些节点中最便宜的添加到“in”集中。
• 重复直到所有节点都在“in”集中。

在您上面给出的图表中，您从节点 A 开始。按照算法，我们查看连接到 A 的所有节点并取最便宜的 (B) 并将其添加到“in”集中。“in”集现在包含 A 和 B。

现在，我们查看连接到“in”集中任何东西的所有节点。这些是节点 D、F、E 和 H。其中，最便宜的是 H，所以我们将 H 添加到我们的“in”集合中，现在是 A、B 和 H。

我们再次查看连接到“in”集中任何东西的所有节点。这些是节点 D、F、E、I 和 G。其中最便宜的是 F，所以我们将其添加进去。

如果您重复此过程直到添加所有节点，并跟踪在此过程中添加了哪些边，您最终将得到整个图形的最小生成树。

希望这可以帮助！