问题标签 [prims-algorithm]

我正在尝试实现 Prim 算法，为此我需要为优先级队列提供 reductionKey 方法（以更新优先级队列中的键值）。我可以在 STL 优先级队列中实现这个吗？

如果有帮助，这就是我正在遵循的算法：

• 对于图 G 中的每个顶点 u
  • 将 u 的键设置为 INFINITY
  • 将你的父级设置为 NIL
• 将源顶点的键设置为 0
• 排队到优先级队列 Q 图中所有顶点与上面的键
• 而 Q 不为空
  • 弹出 Q 中键最低的顶点 u
  • 对于你的每个相邻顶点 v
    • 如果 (v 还在 Q) 并且 (key(u) + weight-function(u, v) < key(v)) 那么
      • 将 u 设置为 v 的父级
      • 将 v 的键更新为等于 key(u) + weight-function(u, v) // 这部分给我带来了问题，因为我不知道如何在优先级队列中实现 reduceKey

首先让我为尺寸道歉，我会尽量保持这个尺寸

在尝试完全按照维基百科上所说的方式构建 prim 算法之后，我发现它不会像我构建的迷宫那样工作。所以我试图做同样的想法来适应我的迷宫，但我看到了一个奇怪的错误，

当我的游戏开始时，它只是没有正确构建我的迷宫，我无法弄清楚为什么这是偶尔发生的事情

其他时候它工作得很好，所以我有一个public Dictionary<int, Dictionary<int, MazeCellState>> maze这个迷宫，当它开始时，迷宫都是树篱，然后我继续像这样建造路径

我不知道为什么有时我会得到上面的图片，我的理论是它最终会恢复它的自我

一些快速说明，此时 MazeCellState 只能是 2 个选项之一，路径或对冲和 reorderList 将重新索引任何类型的列表，迷宫大小是从屏幕分辨率计算出来的，每个单元格是 64x64 PX，

好的，所以对于我的算法类中的一个项目，我想从 .txt 文件中读取迪士尼乐园地图中的所有点，然后使用 prims 算法来解决 MST 问题。

我的问题是我使用“”分隔符将文件中的值解析为临时数组，然后将它们推送到列表中。一切工作正常，花花公子，直到将数组推入列表，然后在程序稍后接收值时，它不返回任何值。我知道这很愚蠢，但希望你们都能提供帮助。

我的代码： http: //pastebin.com/rS6VJ6iJ

迪士尼乐园.txt：http: //pastebin.com/f78D0qrF

我知道这很愚蠢，但我现在无法弄清楚。

编辑：

现在我变得乱码，因为程序正在读取文件末尾的空白行，因为没有值乱码：id：84�������1222����422） ����明日世界露台�����ӿ����

更新了导致错误的部分代码：

我正在使用Prim 算法和 Java 中的 PriorityQueue来研究最小生成树。但是，我弄错了总重量（树的最小重量）。

我是否误解了总重量背后的概念，还是我的代码有问题？

我希望找到图 G 的最小生成树，使其包含边 e，并且它的权重是所有具有边 e 的生成树中的最小值。如果我包含边 e，然后运行 ​​prime 或 kruskals，它会工作吗？

假设图 G 中的边权重均匀分布在 [0,1) 上。哪种算法 prims 或 Kruskals 会更快？我认为这将是 kruskals，因为我们可以利用特定的排序算法，因为排序是 kruskals 算法的瓶颈步骤。

非平面图中是否存在最小生成树？我已阅读有关 prim 算法和三角不等式的信息，但我的图表不满足三角不等式？

我正在研究 Prim 算法。代码中有一部分，穿过切割的下一个顶点将到达属于MST. 在这样做的同时，我们还必须“更新另一组中与离开顶点相邻的所有顶点”。这是来自的快照CLRS：

有趣的部分在于第 1 行。11. 但是由于我们在这里使用的是堆，所以我们只能访问最小元素，对吧 ( heap[0])？那么我们如何从堆中搜索和更新顶点，即使它们不是最小的顶点，因此我们知道它们在哪里，除了线性搜索？

所以我得到了这个 Prims-Algorithm 的伪代码，

//TODO 中的内容

我正在使用 NGenerics 的 Prim 算法来找到连接一些顶点的最小生成树。这就像在每个顶点都连接到每个其他顶点的图上搜索 MST，这意味着边比顶点多，我应该使用 Prim 算法（而不是 Kruskal 算法）。Prim 的算法，如果实施得当，具有 O(|E| + |V| log |V|) 时间复杂度。由于 NGenerics 是一个众所周知的库，它可能具有 Prim 算法的最佳实现，或者至少比 O(|V|^2) 更好。

但是，有一个问题：
如果我想使用 NGenerics 库，我必须将我的图形的所有边添加到 NGenerics 图形数据结构中。像这样的东西（这是伪代码）：

但是，这部分代码显然具有 O(|V|^2) 时间复杂度，这比使用具有更好算法实现的库的目的要好。好吧，不是真的，因为常量也有影响，但我的算法现在是 O(|V|^2) 仍然令人沮丧。

无论如何，我在这里错过了什么吗？我可以在 O(|E| + |V| log |V|) 中完成这项工作吗？