0

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

我实现了一个最小堆，它接受一个整数，我们可以提取最小、减少键和插入键。

现在，正如我在 Prim 中所了解的那样，我需要维护每个顶点的权重、邻居信息。我的一些想法是：

1]定义一个结构

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

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

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

基本上，如果我必须做减少键（v），如何在基于权重的最小堆队列中找到 v。那么有什么优雅的方法可以做到这一点吗？哪个还能保留复杂性？

4

1 回答 1

1

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

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

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

  1. 首先，您的优先级队列需要公开某种迭代器，它允许O(1)访问。为此，您可以boost.Heap直接使用（参见下面的注释），或者从那里了解界面的外观。

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

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

Item 3. 表示您需要在上面的代码中添加以下内容。

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

请注意，这如何让您将优先级队列与其他数据结构分离。当您执行 a decrease_key，并且您node在优先级队列中移动时，您无需担心任何事情，因为每个节点都包含该label成员。

说了这么多，您还应该考虑简单地使用已经具有 Prim 算法的Boost Graph Library 。

于 2015-05-16T07:16:37.177 回答