问题标签 [prims-algorithm]

我正在使用 Prim 算法和优先级队列解决图表。我得到了一个包含处理边和图形本身的代码的类。我还需要使用优先级队列来查找最小生成树。

各位大佬遇到这样的问题怎么解决？您会获取每个节点的所有边，将其放入优先级队列，然后从那里开始吗？

我正在学习最小生成树。我通过 Prim 的加权有向图算法。

算法很简单

• 您有两组顶点，已访问和未访问
• 将所有边的距离设置为无穷大
• 从未访问集中的任何顶点开始并探索其边缘
• 在所有边中，如果目标顶点未被访问并且边的权重小于目标顶点的距离，则使用边的权重更新目标顶点的距离
• 选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问

相信通过上述算法，我将能够在所有生成树中找到成本最小的生成树，即最小生成树。

但是我将它应用于以下示例，我认为它失败了。

考虑以下示例

顶点是 {v1,v2,v3,v4,v5} 和权重为
(x,y) 的边：w =>
(v1,v2) : 8
(v1,v3) : 15
(v1,v4) : 7
(v2, v5) : 4
(v4,v5) : 7

首先我探索v1，它有到v2，v3，v4的边，所以图变成
顶点v1被访问并且（顶点，距离）=>
（v2，8）
（v3，15）
（v4，7）

现在v4的距离最小即7，所以我探索v4，它对v5有优势，所以会发生以下修改
访问顶点v4并且（顶点，距离）=>（v5,7）

现在在所有 v5 中距离最短，即 7 ，所以我探索 v5 并且它没有任何边缘，所以我只是将它标记为已访问

访问顶点 v5

现在，混乱从这里开始

距离最小的顶点现在是 v2，它的边到 v5，权重为 4，当前 v5 的距离为 7，之前由边 (v4,v5) : 7 分配，所以，我相信要制作最小生成树, v5 的距离应该从 7 更新到 4 为 4 < 7 但它不会因为 v5 已经被访问过并且 Prim 算法不更新已经访问过的顶点的距离并且 v5 的距离将保持 7 而不是 4而且这棵树不会有最低成本

我做对了吗？还是我做错了什么？

谢谢

Prim 和 Kruskal 的算法用于找到连通图和无向图的最小生成树。为什么不能在有向图上使用它们？

Prim 的算法是否可以通过 treaps 来实现以加快执行速度，因为正常的堆会在更新键的值时产生问题，同时将顶点存储在堆中，否则需要 O(V) 空间来存储堆中顶点的位置？

在这里看到的 PriorityVertex 类型是什么？我也在写一个 getMinSpanningTree 方法。

Prim 算法

我在让 Prim 的这种实现来跟踪它找到的最短路径的总权重时遇到了一些麻烦。路径似乎是正确的，但我无法弄清楚在将权重添加到存储路径的数组中时将它们求和的位置（因为它只是为了存储使用的路径而编写的）。

我尝试将 pCrawl->weight 求和，因为每个顶点都添加到 MST 中，但这似乎是图表上所有权重的总和。与值 key[] 相同。

我的问题是每次将路径添加到 MST 时可以求和什么，以反映添加所有最短路径时 MST 的总权重。

这是我正在使用的代码：http: //pastebin.com/TFLGCE0L

我制作的邻接表：http: //pastebin.com/SvgGjEPj

以及用于创建它的地图：地图

Prim 的函数如下所示：

使用的结构如下所示：

我觉得我在这门数据结构课程中不知所措，因此尝试使用互联网上的代码来解决这一小部分作业而没有充分理解：/

谢谢，

迈克尔

我正在考虑使用 Prim 的算法来优化水管问题。当找到具有相邻顶点的边时，我非常困惑如何初始化邻接矩阵。每当存在优势时，我都会考虑增加重量。然而，w(Vi,Vj) 本身看起来是一个权重矩阵。那么，为什么我首先需要 A{Vi,Vj}。

我打算做的只是编写一种算法方法，然后继续编写程序。请建议以下是否可以？

1. 设置邻接矩阵 A{Vi,Vj}。这里 Vi 包含访问过的所有节点，Vj 包含访问过的与 Vi 相邻的所有节点。下面的矩阵将存储通过一定距离与相邻的一对房屋相连的所有房屋对。我很困惑

   for each Vi:=1 to n do //Vith 是存储一对房子的第 i 个顶点 对于每个 Vj:=1 to n do //Vjth 是相邻的一对有一定权重的房子 if (edge 存在于 Vi 和Vj) 然后 用 w(Vi,Vj)设置A{Vi,Vj} else if (Vi 和 Vj 之间不存在边) 然后 设置A[Vi,Vj]:=0

2. 计算最小生成树。

3. 输出：显示所需的总水管。

我正在尝试在我的图形程序中实现 Prims 算法，但我遇到了一些困难。我正在遵循在此站点上找到的指南。

它似乎在某种程度上工作正常，但指南输出是：

我的解决方案正在返回：

而且我真的无法弄清楚我的代码有什么问题。

我的代码是：

我目前正在使用 prim 算法在 Unity 中生成一个随机迷宫。

如果我运行游戏，这就是迷宫的样子。

这就是我想要迷宫的样子。

不同之处在于，第一个具有接触的白色方块的角，而第二个始终在白色方块之间留有空间。

这是控制迷宫视觉创建的代码：

欢迎任何解决方案，无论是微小的更改还是对所有代码的完全修改。如果您不知道如何修复代码，但您知道如何使用 prim 算法按照我想要的方式制作迷宫，请分享。

我目前有一个编程任务：给定一个大的加权无连接图（1 < V < 2000, 0 < E < 100 000）。沿着从“源”到点“目的地”的最小加权路径找到最大加权边。

到目前为止，我将图形存储在 AdjacencyList 中（IntegerPair 的向量的向量，其中第一个整数是邻居，第二个是边的权重）。

我还通过使用 Prim 算法获得了最小生成树：

我现在坚持的是如何找到从源到目的地的路径并在以下查询中返回最大权重边缘：

有人告诉我使用深度优先搜索来遍历生成的 MST，但我认为 DFS 将遍历所有不在正确路径上的顶点（对吗？）。以及如何找到最大边缘？

（这个问题与任何 SSSP 算法无关，因为我没有学过 Dijstra 等）