问题标签 [prims-algorithm]

我的项目是使用java实现最小生成树。我的目标是使用 Prim 的算法来完成这项任务。

该图的定义是 G = (V, E) 其中 V 是引脚集合，E 是引脚对之间可能互连的集合，对于 E 中的每条边 (u,v)，我们有一个权重 w( u,v) 指定连接 u 和 v 的成本。

我的想法是使用两个哈希图。首先将 pin 作为键，将邻居列表作为值。第二个哈希图将边缘列表（u，v）作为键，值将是它的权重。

您认为存储图表的最佳方式是什么？

我正在尝试编写一个程序，该程序将使用 Kruskal 和 Prim 算法找到给定无向加权图的 MST。我已经在程序中成功地实现了 Kruskal 的算法，但是我遇到了 Prim 的问题。更准确地说，我不知道如何实际构建 Prim 函数，以便它遍历图中的所有顶点。我在程序执行期间遇到了一些 IndexOutOfBoundsException 错误。我不确定其他人需要多少信息才能了解我到目前为止所做的事情，但希望不会有太多无用的信息。

这是我到目前为止所拥有的：

我有一个Graph,Edge和一个Vertex类。

• 顶点类大多只是一个包含顶点名称（编号）的信息存储。

• Edge 类可以创建一个具有获取参数的新 Edge (Vertex start, Vertex end, int edgeWeight)。该类具有返回通常信息的方法，例如开始顶点、结束顶点和权重。

• Graph 类从文本文件中读取数据并将新边添加到 ArrayList。文本文件还告诉我们图形有多少个顶点，并且也被存储了。

在Graph课堂上，我有一个 Prim() - 应该计算 MST 的方法：

findClosesNeighbour() 方法如下所示：

ArrayList<Vertex> visited并ArrayList<Edges> graph在创建新图形时构建。

Visited() - 方法只是一个布尔检查，看看 ArrayList 是否包含我们正在考虑移动到的顶点。我findClosestNeighbour()独立测试了它，它似乎正在工作，但如果有人发现它有问题，那么也欢迎反馈。

主要是正如我提到的，我的问题是在 Prim() 方法中实际构建主循环，如果需要任何其他信息，我很乐意提供。

谢谢你。

编辑：澄清我的 Prim() 方法的思路是什么。我想要做的是首先随机化图中的起点。之后，我会找到离该起点最近的邻居。然后我们将连接这两个点的边添加到 MST，并将顶点添加到访问列表中以供稍后检查，这样我们就不会在图中形成任何循环。

这是引发的错误：

第 203 行：return neighbour.get(0);在 findClosestNeighbour() 中

第 179 行：Edge e = findClosestNeighbour(startingVertex);在 Prim() 中

我正在尝试使用 boost 的 prim 算法来使用边权重和 id 号而不是边权重来找到最小生成树。

例如，如果两个边的权重都是 1，则将比较 id，无论哪个较小，都会打破平局。

我创建了一个 EdgeWeight 类并重载了 < 和 + 运算符来执行此操作，然后将 edge_weight_t 属性从 int 更改为 EdgeWeight，希望它能起作用。

我收到一个错误，“c:\program files (x86)\microsoft visual studio 10.0\vc\include\limits(92): error C2440: '' : cannot convert from 'int' to 'D' 1> No constructor could取源类型，或构造函数重载决议不明确”

我这样做对吗？有一个更好的方法吗？

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

编辑：好的，所以我现在使用 cjm 的扰动方法实现了权重，但是将来我相信我将不得不以某种方式使用上述方法，仍然想知道该怎么做

编辑2：根据耶利米的回应，我将 vertex_distance_t 从 int 更改为 EdgeWeight 但得到了同样的错误

在您已经知道任何给定权重的最小值的情况下，如何修改 prim 的算法？例如，如果一个图由边权重 0 和 1 组成，如何让 prim 的算法更快？

Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible. I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algorithm in O( m*a(m,n)).

I have no idea how to do this and really need some guidance about how the weights can help me in here.

我正在尝试实现 Prim 迷宫生成算法：

• 从一个充满墙壁的网格开始。
• 选择一个单元格，将其标记为迷宫的一部分。将单元格的墙壁添加到墙壁列表中。
• 虽然列表中有墙：
  • 从列表中随机选择一面墙。如果对面的牢房
    还没有进入迷宫：
    • 使墙壁成为通道，并将另一侧的单元格标记为迷宫的一部分。
    • 将单元格的相邻墙添加到墙列表中。
  • 如果对面的牢房已经在迷宫中，则将墙从列表中删除。

删除一些实现细节，我的实现如下所示：

是带有单元格的矩阵。每个单元格都有左/右/上/按钮墙。边界墙标记为boolean frontier并且不是实施的一部分，因为我想保持我的迷宫框架。

我的问题是我的迷宫没有完成，并不是所有的单元格都被遍历了。有时只遍历了几个单元格，几乎所有单元格都完成了。我相信我错过了一些无法弄清楚的东西。

请帮忙。

部分穿越的迷宫见下图。

我正在尝试使用类似于许多在线资源的伪代码使用优先级队列创建 Prim 算法的 C 实现。最终目标是（希望）一些漂亮的迷宫生成。我只是对实施的细节感到困惑。

输入：具有随机权重的邻接矩阵

期望输出：最小生成树的邻接矩阵

*编辑：添加了我的（不工作）尝试。我仍然得到一棵不正确的树，我不确定我哪里出错了。我想我会从对这段代码的另一组眼睛中受益。

我正在使用 C 语言中的 Prim MST，该函数采用邻接矩阵。考虑到重量当然在A[i][j].

假设我有一个前驱数组，可以追踪我到目前为止找到的最小边。 predecessor[u]=v{这也是最终的 MST}

现在我想修改当前A[i][j]矩阵并将权重更改为 1。也就是说，边（索引）也存在于前驱数组中。否则，我将其更改为零。

我该怎么做？这是我的解决方案：

我在教科书中偶然发现了这个问题：

“一般来说，Prim、Kruskal 和 Dijkstra 算法的时间复杂度取决于什么？”

一个。图中的顶点数。
湾。图中的边数。
C。两者都是关于图中顶点和边的数量。

解释你的选择。

因此，根据 Wikipedia Prim、Kruskal 和 Dijkstra 的算法，最坏情况的时间复杂度分别O(ElogV)为O(ElogV)和O(E+VlogV)。所以我猜答案是c？但为什么？

我想知道是否可以通过在该图上执行 Prim 算法来提供图 G 的任何最小生成树？

Prim 算法是否为我们提供了所有可能的 MST？