问题标签 [prims-algorithm]

优先级队列中的EXTRACT-MIN操作和操作之间的关系是什么？DECREASE-KEY我在使用 Prim 算法的最小跨度问题的讲座中遇到了这个问题。

麻省理工学院的教授在视频中的 01:07:16 秒时提到了它，但我不明白。有人可以帮我解决这个问题吗？

PS：否则我对我对优先队列的理解感到满意。

我在过去一天一直在努力完成的编程课上遇到了这个问题……而且我真的不知道该怎么做。

我了解 Prim 算法的基本概念：

我已经获得了一个 Graph 的实现（使用邻接列表）来实现 Prim 的算法。问题是我不太了解实现。到目前为止，我对实现的理解如下：

作为一个邻接列表，我们有数组形式的所有节点： 链接到它的是一个链接列表，包含权重、目的地和指向特定节点其余链接的指针的详细信息：

看起来有点像这样的东西：

我们还有一个“Edge”结构，我认为它应该使实现变得更简单，但我并没有真正看到它。

这是给出的代码：

GRAPH.h 界面：

GRAPH.c 实现：

为清楚起见，file 以从文件中获取测试数据：

提前致谢。

卢克

完整文件：http ://www.cse.unsw.edu.au/~cs1927/12s2/labs/13/MST.html

更新：我对这个问题进行了另一次尝试。这是更新的代码（上面的一个编辑将graph_client.c更改为使用我编写的“GRAPHmstPrim”函数。

GRAPH_adjlist.c::

更改摘要： - 添加了 edgeList 以保存可能进入 MST 的边 - 数组 nodeIsConnected[] 以跟踪节点是否在 MST 中 - 选择最小节点的函数。如果没有不复制链接的节点，则返回 NULL

有人可以向我解释为什么使用相邻矩阵的 Prim 算法会导致时间复杂度为0 吗？O(V2)

Prim 和 Kruskal 的算法都产生最小生成树。根据割属性，对于这些算法，树的总成本将是相同的，但是这两种算法是否有可能以相同的总成本给出不同的 MST，因为我们在面临多个选择时按字母顺序选择它. 例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A->B 中的 A 和 B->C 中的 B。

谢谢

我正在使用邻接矩阵，优先级队列是数据结构。

根据我的计算，复杂度是V^3 log V：

• While循环：V
• 检查相邻顶点：V
• 如果条目已经存在，则检查队列并更新：V log v

但是，我到处都读到复杂性是V^2

请解释。

我查看了以下 prim 的算法（为了创建最小生成树），我不确定以下代码中的输入值 s 是什么，我认为 G 当然是发送的图（邻接矩阵或列表图），我认为值 s 应该从哪里开始？此外，如果它是开始，那么您将以何种方式将起始值发送到以下算法？：

任何帮助将不胜感激，谢谢！

其中最有效的数据结构是什么：

• 边缘列表
• 邻接表
• 邻接矩阵

用于执行 Prim-Jarnik 算法，为什么？

可能的重复：
Kruskal vs Prim

你什么时候会使用 Kruskal 算法而不是 Prim 算法来找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，在空间和时间方面使用其中一种更有效？

他们的特定输入是否使一个比另一个好得多？

Dijkstra 和 Prim 算法之间的确切区别是什么？我知道 Prim 会给出一个 MST，但 Dijkstra 生成的树也将是一个 MST。那么具体的区别是什么？

我正在尝试使用 C++ 和矩阵来实现 Prim 的算法。

这是我的问题：

cNode 是起始节点。

graph[][]是保持连接的二维矩阵。

nodeCon[]是将保存 MST 连接的数组（哪个节点与其他节点连接）

node[]=保存 nodeCon 的成本值。

我的问题是我将如何继续下一跳？假设我找到了最小连接，我将设置cNode= minConnection循环的外观？我怎么知道我检查了所有节点？

提前致谢