个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
25
4
我正在研究 Prim 算法。代码中有一部分穿过切割的下一个顶点将进入属于 MST 的顶点集。在这样做的同时，我们还必须“更新另一组中与离开顶点相邻的所有顶点”。这是 CLRS 的快照:
有趣的部分在于第 1 行。 11. 但是因为我们在这里使用堆，所以我们只能访问最小元素，对吧 (heap[0])？那么我们如何从堆中搜索和更新顶点，即使它们不是最小的顶点，因此除了通过线性搜索之外我们知道它们在哪里？
最佳答案
可以构建支持称为decrease-key 操作的优先级队列，该操作采用优先级队列中现有对象的优先级并将其降低。现有库附带的大多数版本的优先级队列不支持此操作，但可以通过多种方式构建它。
例如，给定一个二叉堆，您可以维护一个辅助数据结构，将元素映射到它们在二叉堆中的位置。然后，您将更新二进制堆实现，以便每当执行交换时，都会更新此辅助数据结构。然后，为了实现 decrease-key，您可以访问表，找到节点在二叉堆中的位置，然后继续冒泡步骤。
其他基于指针的堆，如二项式堆或 Fibonacci 堆明确支持此操作(Fibonacci 堆是专门为此设计的)。您通常有一个从对象到它们在堆中占据的节点的辅助映射，然后可以重新连接指针以在堆中移动节点。
希望这对您有所帮助!
关于algorithm - 如何为 Prim 算法更新堆中的元素优先级？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17075497/
25
4
0
我正在尝试用 javascript 创建一个随机迷宫生成器。 可能已经有可用的示例，但我正在尝试自己解决这个问题(好吧，尽可能多) 我遇到的问题是我的脚本只运行了几个 block 然后就停止了。 我认
一 点睛 在生成树的过程中，把已经在生成树中的节点看作一个集合，把剩下的节点看作另外一个集合，从连接两个集合的边中选择一条权值最小的边即可。 二 算法介绍 首先任选一个节点，例如节点1，把它放在集合
“因此，Prim 算法的总时间为 O(V lg V + E lg V) = O(E lg V)，这与我们实现 Kruskal 算法的渐进时间相同。” 来自http://serverbob.3x.ro/
def prim(graph): que = queue.PriorityQueue() mst = [] visited = set() # Generate edg
我正在尝试使用优先级队列在 Java 中实现 Prim 的算法。 我找不到我的错误。 :/我只是认识到队列没有正确排序节点。 图表示例: 0 4 7 5 4 0 2 3 7 2 0 1 5 3 1 0
我的算法课正在讨论 Prim 算法作为一种寻找加权图的最小生成树的方法。我们的教授让我们试着想一个图的例子，Prim 的算法需要 N^2 时间来解决(N = 顶点数)。类没有人能凭空想到一个，所以我问
prim 算法的简单实现应该给出 O(mn) 的运行时间。但我在 Prim 函数中有 3 个 for 循环(使运行时间立方)。我哪里出错了？ void Graph::Prim (const int s
我正在尝试实现一种近似算法来解决旅行商问题 (TSP)，当三角不等式对边权重成立时可以使用该算法。正如 Cormen 等人在算法简介(第 3 3d.)中所述，伪代码是: 这是一个例子: 我苦恼的是如何
我发现 there are two ways to implement Prim algorithm ，并且邻接矩阵的时间复杂度为 O(V^2)，而堆和邻接列表的时间复杂度为 O(E lg(V))。
我正在查看 Wikipedia entry对于 Prim 的算法，我注意到它与邻接矩阵的时间复杂度是 O(V^2)，它与堆和邻接列表的时间复杂度是 O(E lg(V))，其中 E 是边数，V 是图中的
我正在尝试使用 Prim 的最小生成树算法优化图形。但我没有得到想要的答案。 算法: 1. Construct min heap array. The array consists of nodes
我有以下函数来查找父数组，以便使用 Prim 算法获得图的最小生成树。 #include #include #include int printMST(int parent[], int n, i
Prim 算法思想： 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。 最小生成树（MST）：权值
这个问题在这里已经有了答案: what is the meaning of "let x = x in x" and "data Float#" in GHC.Prim in Haskell (2 个
所以我检查了之前发布的 prims 算法帖子。我找不到一个能满足老师要求的。我和他一起编写了这段代码，并且大部分工作正常。然而，由于某种原因，当它到达某个点时，它会破裂并走向错误的边缘。 '''pub
我必须从 Prim 算法创建一个迷宫，更准确地说是使用这个算法:(随机 Prim 算法)。 http://en.wikipedia.org/wiki/Maze_generation # Randomi
我正在尝试使用 Prim 算法实现一个随机生成的迷宫。但是该程序无法正确生成迷宫。请看看并给我一些建议 这是我的迷宫图片: 迷宫应该是这样的: Prim 算法: private void Prims(
我正在一个项目中使用 Dijkstra 算法，但想尝试使用策略模式实现 Prims 算法，看看它有什么更好的地方，但我不确定如何使用策略模式。我以前从未使用过模式，所以我不知道从哪里开始。 packa
我正在尝试将房间放置在 ASCII 屏幕上，然后使用 Prim's algorithm用迷宫“填充”房间之间的空间，但实际上并没有闯入房间。我已经修补了几个小时，但我无法找到一种方法来阻止我的算法闯入
我正在尝试使用 JGraphT 实现 Prim 的最小生成树算法。看起来怎么样？ 我遇到的一个问题是 JGraphT 按照指示处理所有事情。因此，有时需要进行一些尴尬的调用来反转 g.getEdgeS
我是一名优秀的程序员,十分优秀！