为Prim的c实现设计数据结构

Question

我正在尝试在C中实现MST的Prim算法。我有一个设计问题

我实现了一个min-heap，它需要一个整数，我们可以提取min、减少键和插入键。

现在，正如我在Prim的理解，我需要维护每个顶点的权重和邻居信息。我的一些想法是:

1]定义结构

struct node {
    int vertex;
    int weight;
    int neighbor;
};

使用min堆以最小权重返回节点。但是问题是减少键，因为对于减少键，调用者需要传递他想要减少键的顶点。由于堆交换元素的频率太高，我必须遍历整个列表以找到顶点，然后减少它的键。这是O（n），我认为如果我这样做，Prim的情况会变得更糟。

2] 另一种方法是维护另一个数组，它跟踪最小堆队列中顶点的位置。但在最小堆操作期间跟踪位置会很麻烦。

基本上，如果我必须执行降键（v），如何在基于权重的min-heap队列中找到v。那么有什么优雅的方法可以做到这一点吗？它仍然可以保留复杂性？

Answer 1

基本上确实需要在数据结构之间进行一些交叉引用。然而，你写

但在最小堆操作期间跟踪位置会很麻烦

这是不正确的。通过使用以下内容，您可以重用或编写不需要的可重用数据结构。

>

首先，您的优先级队列需要公开某种迭代器，它允许 O（1） 访问。为此，您可以使用提升。直接堆砌（请参阅下面的注释），或者从那里获得有关界面外观的想法。

现在您使用另一种数据结构，它将（在O（1）中）节点标签映射到队列的迭代器。例如，如果节点标签是（连续的）整数，您可以使用迭代器的向量；如果它们基本上是其他任何东西，您可能应该使用unordered_map。

每个节点结构还需要包括2中数据结构使用的标签。

项目3。意味着您需要在上面的代码中添加以下内容。

struct node {
     ...
     // Identifies
     Label label;
};

请注意这是如何允许您将优先级队列与其他数据结构分离的。当您执行< code>decrease_key时，您的< code >节点在优先级队列中移动，您不需要担心任何事情，因为每个节点都包含< code>label成员。

说了这么多，你还应该考虑简单地使用已经有Prim算法的Boost图形库。