在c中设计Prim实现的数据结构

提问于 2024-04-28T01:29:07+08:00

浏览次

0

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

我实现了一个带有整数的min-heap，我们可以提取-min，减少key和insert-key .

现在正如我在Prim中所理解的那样，我需要保持每个顶点的权重，邻居信息 . 我的一些想法是：

1]定义结构

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

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

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

基本上，如果我必须执行减少键（v），如何在基于权重的最小堆队列中找到v . 有没有优雅的方法来做到这一点？哪些仍然可以保持复杂性？

1 回答

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

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

这不是正确的 . 使用以下命令，您可以重用或编写不需要此功能的可重用数据结构 .
- 首先，您的优先级队列需要公开某种iterator，它允许O（1）访问 . 为此，您可以直接使用boost.Heap（请参阅下面的注释），或者从那里了解界面的外观 .
- 现在您使用另一个数据结构，该结构将（在O（1）中）节点标签映射到队列的迭代器 . 例如，如果节点标签是（连续的）整数，则可以使用 vector 的迭代器;如果它们基本上是其他任何东西，你应该使用 unordered_map .
- 每个节点结构还需要包含数据结构在2中使用的标签 .
第3项意味着您需要在上面的代码中添加以下内容 .
```
struct node {
     ...
     // Identifies
     Label label;
};
```
请注意这是如何允许您将优先级队列与其他数据结构分离的 . 当您执行 decrease_key ，并且 node 在优先级队列中移动时，您不需要担心任何事情，因为每个节点都包含 label 成员 .

说完所有这些之后，你还应该考虑使用已经有Prim算法的Boost Graph Library .
回复于 2024-04-28T01:29:07+08:00

相关问题