问题标签 [prims-algorithm]

我这里有一个最小堆类，它根据权重属性存储 Link 对象。我的目标是能够直接访问和更改存储在最小堆中的对象的属性。我需要能够仅基于“loc”属性访问这些对象。
因此，例如，我可能想要访问 loc 值为 6 的 Link 对象并更改其父属性或权重属性；但是我只知道它在访问时的 loc 属性值。
我的理解是我应该使用指向这些对象的指针数组，但我不确定我将如何实现它。

谢谢！

假设图中的所有边权重都是 1 到 |V| 范围内的整数。你能让 Prim 的算法运行多快？如果对于某个常数 W，边权重是 1 到 W 范围内的整数怎么办？

根据我的教科书：

Prim 算法的运行时间取决于我们如何实现最小优先级队列 Q。如果我们将 Q 实现为二进制最小堆，我们可以使用 BUILD-MIN-HEAP 过程在 O(V) 中执行第 1-5 行时间。while 循环的主体执行 |V| 次，并且由于每个 EXTRACT-MIN 操作需要 O(lg V) 时间，所以对 EXTRACT-MIN 的所有调用的总时间为 O(VlgV)。第 8-11 行中的 for 循环总共执行 O(E) 次，因为所有邻接列表的长度之和为 2|E|。在 for 循环中，我们可以在第 9 行中通过为每个顶点保留一个位来判断它是否在 Q 中，并在顶点从 Q 中删除时更新该位，从而在恒定时间内实现对 Q 中的成员资格的测试。第 11 行的赋值涉及对最小堆的隐式 DECREASE-KEY 操作，二进制最小堆在 O(lg V) 时间内支持该操作。因此，

第 1-4 行需要 O(V) 时间。我已经阅读了一些解释为什么 BUILD-MIN-HEAP 过程需要线性时间，但我还没有理解它们。你能解释一下为什么 MIN-HEAP 过程的时间复杂度是 O(V) 吗？

此外，我认为在最小堆中，最小元素位于根部。那么，为什么每个 EXTRACT-MIN 操作都需要 O(lg V) 时间？

然后，for 循环执行 O(Σ_{v in VG} deg(v)) 次，对吧？你能解释一下为什么 Σ_{v in VG} deg(v)=2E 吗？

此外，如果我们知道对于某个常数 W，边权重是从 1 到 W 范围内的整数，会有什么不同？

编辑：

假设图中的所有边权重都是 1 到 |V| 范围内的整数。你能让 Prim 的算法运行多快？

我们可以对上述算法进行哪些更改，以使 Prim 算法尽可能快地运行？

我正在尝试使用优先级队列在 Java 中实现 Prim 算法。

我找不到我的错误。：/我只是认识到队列没有正确排序节点。

图表示例：

它总是将节点 4 作为第二个节点。所以它像[node1，node4，node2，node3]而不是[node1，node2，node3，node4]对队列进行排序。我对优先级队列做错了什么？

问候

我正在寻找 Prim 算法的图形的良好表示。

例如表示 BFS 的图

优雅简洁，它将每个顶点映射到邻居队列。

对于 Dijkstra，它有点复杂（权重在表示中）

• 使用优先队列。

然而，如果在 Prim 的算法中遵循类似的结构，则还需要存储每条边的源，并且如果图形表示如下：

然后存储了冗余信息（源/来自顶点）。

欢迎任何有关 Prim 算法的 C++ 中最佳图形表示的建议！

ps：当然可以将图表示为，std::vector<from_to_weighted_edge>但不会有 O(1) 的邻居查找，这是所有常见图表示的共同特征。

我正在尝试在 C++ 中实现 Prim 的 MST 算法。我有一个设计问题

我实现了一个最小堆，它接受一个整数，我们可以提取最小、减少键和插入键。

现在，正如我在 Prim 中所了解的那样，我需要维护每个顶点的权重、邻居信息。我的一些想法是：

1]定义一个结构

使用最小堆返回具有最小权重的节点。但问题是减少键，因为对于减少键，调用者需要传递他想要减少键的顶点。由于堆交换元素过于频繁，我必须遍历整个列表才能找到顶点，然后减少它的键。这是 O(n)，我认为如果我这样做，Prim 会变得更糟。

2] 另一种方法是维护另一个数组，该数组跟踪最小堆队列中顶点的位置。但是在最小堆操作期间跟踪位置会很麻烦。

基本上，如果我必须做减少键（v），如何在基于权重的最小堆队列中找到 v。那么有什么优雅的方法可以做到这一点吗？哪个还能保留复杂性？

每个人。希望有人能帮助我。我有一个代码可以在 openMP 上并行 Prim 的算法，我需要让它在 Xeon Phi 上工作。请帮我。我无法真正理解如何做到这一点。这是我在 openMP 上的代码。

我有以下函数来查找父数组，以便使用 Prim 算法获得图的最小生成树。

但是父数组的所有值都是'0'（零），不知道条件哪里出错了。

我是一名 Java 开发人员（但来自非 CS/IT 教育背景）。我对算法产生了兴趣，目前我正在尝试实现 Prim 的算法来计算 MST。为了让您了解上下文，我已经告诉了这一点，但我的问题与 MST 无关。

我已经实现了自己的 MinHeap 而不是使用 Java.util.PriorityQueue （尽管即使我更改了代码并使用它，我也面临着前面提到的相同问题）。

我将项目添加到堆中，但即使在将项目添加到堆中之后，决定比较的项目的值也会发生变化。现在，一旦值更改，堆就不会更改，因此在删除项目时，我会弹出错误的项目。

这种情况怎么办。。

我正在粘贴我的代码以供参考。我在 MinHeap 中添加 Vertex 类型的项目。每个 Vertex 都有一个关联的“int cost”，用于比较 Vertex 的两个对象。现在我在堆中添加顶点对象，并且根据“成本”的当前值调整堆，但是一旦添加了顶点对象，那么如果它的成本发生变化，那么我需要帮助来了解如何调整并让它反映在我的堆中. 请在这方面帮助我，如果我走错了方向，请纠正我。

所以我有这张图

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

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

提前谢谢各位。

我们可以通过将算法更改为选择最大顶点而不是选择最小顶点来计算最大生成树吗？

我通过否定边缘并应用正常的 Prim 的最小生成树算法遇到了解决方案。