在 Prim 算法中卡住并 运行 出节点？
Getting stuck and running out of nodes in Prim's algorithm?
所以我有这张图
我正在尝试构建它的最小生成树。从顶点 A 开始，我走 A-B-F-E-D，然后就没有地方可去了，考虑到 D 的所有相邻顶点都已经是树的一部分，我该如何继续前进？
另外，如何计算新边的值范围以成为最小生成树的一部分？
在此先感谢大家。
我认为您对 Prim 算法的工作原理有点误解。根据您上面的描述，您认为 Prim 的算法是这样工作的：
- 从任意节点开始。
- 查看当前节点连接的所有你还没有访问过的节点。
- 转到这些节点中最便宜的节点。
- 重复直到覆盖所有节点。
这与 Prim 算法的工作原理接近，但并不完全正确。在 Prim 的算法中，没有 "current" 节点的概念。相反，您有两组节点：已添加的节点和未添加的节点。 Prim 的算法是这样工作的：
- 从任意节点开始。将其添加到 "in" 集合。
- 查看连接到 "in" 集但尚未添加到 "in" 集的所有节点。
- 将这些节点中最便宜的节点添加到 "in" 集合。
- 重复直到所有节点都在 "in" 集合中。
在您上面给出的图表中，您从节点 A 开始。按照算法，我们查看连接到 A 的所有节点并选择最便宜的 (B) 并将其添加到 "in" 集合。 "in" 集合现在包含 A 和 B。
现在，我们查看 "in" 集中连接到 anything 的所有节点。这些是节点 D、F、E 和 H。其中，最便宜的是 H，因此我们将 H 添加到我们的 "in" 集合中，现在是 A、B 和 H。
我们再次查看连接到 "in" 集合中的 anything 的所有节点。这些是节点 D、F、E、I 和 G。其中最便宜的是 F，因此我们将其添加到其中。
如果重复此过程直到添加所有节点，并跟踪在此过程中添加了哪些边，最终将得到整个图的最小生成树。
希望对您有所帮助！
所以我有这张图
我正在尝试构建它的最小生成树。从顶点 A 开始，我走 A-B-F-E-D，然后就没有地方可去了，考虑到 D 的所有相邻顶点都已经是树的一部分，我该如何继续前进？
另外，如何计算新边的值范围以成为最小生成树的一部分？
在此先感谢大家。
我认为您对 Prim 算法的工作原理有点误解。根据您上面的描述，您认为 Prim 的算法是这样工作的：
- 从任意节点开始。
- 查看当前节点连接的所有你还没有访问过的节点。
- 转到这些节点中最便宜的节点。
- 重复直到覆盖所有节点。
这与 Prim 算法的工作原理接近，但并不完全正确。在 Prim 的算法中，没有 "current" 节点的概念。相反，您有两组节点：已添加的节点和未添加的节点。 Prim 的算法是这样工作的：
- 从任意节点开始。将其添加到 "in" 集合。
- 查看连接到 "in" 集但尚未添加到 "in" 集的所有节点。
- 将这些节点中最便宜的节点添加到 "in" 集合。
- 重复直到所有节点都在 "in" 集合中。
在您上面给出的图表中，您从节点 A 开始。按照算法，我们查看连接到 A 的所有节点并选择最便宜的 (B) 并将其添加到 "in" 集合。 "in" 集合现在包含 A 和 B。
现在，我们查看 "in" 集中连接到 anything 的所有节点。这些是节点 D、F、E 和 H。其中，最便宜的是 H，因此我们将 H 添加到我们的 "in" 集合中，现在是 A、B 和 H。
我们再次查看连接到 "in" 集合中的 anything 的所有节点。这些是节点 D、F、E、I 和 G。其中最便宜的是 F，因此我们将其添加到其中。
如果重复此过程直到添加所有节点，并跟踪在此过程中添加了哪些边，最终将得到整个图的最小生成树。
希望对您有所帮助！