问题标签 [prims-algorithm]

我必须在 boost 库中使用 kruskals 算法来找到最小生成树的权重。我想我成功了

现在我需要找到顶点 0 和离它最远的那个之间的距离（权重总和）？关于我该怎么做的任何提示？

我正在考虑使用顶点迭代器，但后来我将权重存储在 weightMap 中，那么如果我遍历图形的顶点，我该如何访问它？

编辑：我修改了我的程序，决定使用 kruskal 和 prim

1.kruskal 用于生成树权重 2.prim 算法用于每个顶点到顶点 0 的距离（在生成树中存储在地图距离中）

不幸的是，出了点问题，距离 [*vertex] 是第三个顶点并没有给出答案 2，而是给出了一个

生成树的权重也是 14 而不是 7

我的虚拟输入是：

这是我的程序：

谢谢你 ：）

我正在尝试使用 STL 在 C++ 中实现 Prim 的 MST 算法。

但是对于下面的程序，它似乎进入了一个无限循环。然后退出并出现错误。

Prim 的 MST 算法的伪代码；

我的代码：

实施此算法的图：

请帮助理解 prims 算法伪代码（在 coreman 和 wiki 中） Prim's algorithm。

我能够理解直到 1 或 while 循环 r.key=0 确保首先扫描根的邻居或相邻节点，但由于 u 已经属于 Q（节点队列直到现在不包括在 prims 最小生成树中）和 v同样在 Q 中，将无助于生成 prims MST。

也是 coreman 和维基状态

在第 6-11 行的 while 循环的每次迭代之前，(v, v.parent) 将 v :: 连接到已经放置在最小生成树中的某个顶点。

因为 A 是我们的 MST，那么 1. 将如何提供帮助，因为 v 已经包含在我们的 MST 中（如 v ∈ V - {r} - Q 所示）为什么应该包含它。

我需要一些关于 Prim 算法问题的帮助：

令 T 为 Prim 算法得到的图 G 的最小生成树。设 Gnew 是通过向 G 添加一个新顶点和一些带权重的边获得的图，将新顶点连接到 G 中的一些顶点。我们可以通过将一个新边添加到 T 来构造 Gnew 的最小生成树吗？如果您回答是，请说明如何；如果不是，请解释原因。

先感谢您！！

我定义一个unordered_map这样的：

有没有一种从 unordered_map 边缘中选择随机边缘的有效方法？

我正在尝试使用优先级队列来实现 prim 的算法。当我调用 offer() 方法时，它给了我一个类转换异常，说顶点不能转换为可比较的。有解决方法吗？

我使用相等的速率编写了一个 Prim 的迷宫生成器，因此它几乎完全是随机的。我已经对该算法进行了基准测试，发现它的运行时间为 O(5n)。这相当于生成 128 x 128 迷宫的 290 秒运行时间。

我的问题是，这是一个好的运行时间吗？这是高、低、平均吗？我有一种感觉，减速更多地与缓存迷宫的节点有关，然后是相对轻量级的整数比较。我只是想知道我是否有一个体面的实现，或者它是否太慢。

我一直在编写一些代码来引导“机器人”通过具有多个死角的迷宫和 1 条通往目标的正确路径，如下所示：

我已经使用堆栈记录机器人第一次到达具有 3 或 4 个可能出口的正方形时所面对的方向，如果所有相邻的正方形都已被访问，则使用 pop() 使机器人从它首先返回的方向返回来自（与到达方向相反）。在运行结束时，堆栈包含到达目标路线上所有方格的方向。按照堆栈的相反方向将机器人从目标带回起点。我正在努力找出如何使用此堆栈，以便在下一次运行时机器人将采用最佳路径到达目标。

我的一些代码：

最佳方法显示了我解决它的尝试，但它所做的只是让机器人在每个路口直行

比如这个迷宫，

会让我留下堆栈：东，东，南，南，东，南，南，东，东，南，南，东，东，东，南，东，南

我写了这段代码来绘制随机图。我一直在徒劳地试图找到如何在图中选择一条线，以便我可以在选择线时应用 prim 算法并查看它们是否找到了最小树。

我在stackoverflow中发现了这个，它没有多大帮助。如何选择在 HTML5 画布上绘制的线条？. 我想知道是否有预先编写的代码，这样我就不需要从头开始编写它了。

我在想是否可以在鼠标移动时找到鼠标的位置，并且每次都检查鼠标的位置是否在线上，如此处Find a point is on a line。请帮助并建议是否有任何预先编写的代码，因为我受时间限制。先感谢您。

我正在尝试解决以下图形练习：

在无向加权图中，有 V 个顶点和 E 条边。找到访问 T(T<=V) 个顶点所需的最小权重，从标记为 0 的顶点开始。此外，如果两个访问过的顶点之间存在边，则其权重设置为 0。

这不是一个经典的旅行商问题，因为添加了一个条件，即如果您访问两个顶点，它们之间的边的权重会减小到 0。

如果 T == V，则使用 Prim 的最小生成树算法解决该问题，但由于您不必访问所有顶点，因此这并不总是返回最小权重。

我考虑过找到最小生成树，然后切割不会妨碍我到达所有“目标”顶点的能力的每条边，但这似乎过度并且可能不正确。

有什么想法吗？

编辑：我会给你一个例子。假设我们有一个带有 4 个顶点标记为 0,1,2 和 3 的图。我们有以下边（从，到，权重）： (0,1,1) (0,2,2) (1,3,4 ) (2,3,1) 最小生成树将包含边：(0,1,1)、(0,2,2) 和 (2,3,1)。有了它，每个顶点都可以从 0 开始到达。但是，练习的目标是达到 T 个顶点。话虽如此，例如，我们可能只需要到达顶点 2 和 3，从而不需要边 (0,1,1)，因此到达目标顶点所需的总权重是 2+1，而不是 1 +2+1。