12

我正在研究 Prim 算法。代码中有一部分，穿过切割的下一个顶点将到达属于MST. 在这样做的同时，我们还必须“更新另一组中与离开顶点相邻的所有顶点”。这是来自的快照CLRS：

在此处输入图像描述

有趣的部分在于第 1 行。11. 但是由于我们在这里使用的是堆，所以我们只能访问最小元素，对吧 ( heap[0])？那么我们如何从堆中搜索和更新顶点，即使它们不是最小的顶点，因此我们知道它们在哪里，除了线性搜索？

4

2 回答 2

9

可以构建支持称为reduction-key操作的优先级队列，该操作采用优先级队列中现有对象的优先级并降低它。现有库附带的大多数优先级队列版本不支持此操作，但可以通过多种方式构建它。

例如，给定一个二进制堆，您可以维护一个辅助数据结构，将元素映射到它们在二进制堆中的位置。然后，您将更新二进制堆实现，以便每当执行交换时，都会更新此辅助数据结构。然后，要实现 reduce-key，您可以访问表，找到节点在二进制堆中的位置，然后继续冒泡步骤。

其他基于指针的堆，如二项式堆或斐波那契堆明确支持此操作（斐波那契堆是专门为它设计的）。您通常有一个从对象到它们在堆中占据的节点的辅助映射，然后可以重新连接指针以在堆中移动节点。

希望这可以帮助！

于 2013-06-12T22:38:21.270 回答
2

指针支持高效的复合数据结构

你有这样的东西（使用伪代码 C++）：

class Node
    bool visited
    double key
    Node* pi
    vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights
    //and extra fields needed for PriorityQueue data structure
    // - a clean way to do this is to use CRTP for defining the base
    //   PriorityQueue node class, then inherit your graph node from that

class Graph
    vector<Node*> vertices

CRTP：http ://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

算法中的优先级队列Q包含类型的项目Node*，其中ExtractMin让你得到Node*最小的key。

您不必进行任何线性搜索的原因是，当您获得 时u = ExtractMin(Q)，您有一个Node*. 这样u->adjacent就可以得到每个相邻节点v的's inG.Adj[u]和w(u,v)'s in const time 。由于您有一个指向优先级队列节点（即）的指针，因此您可以以每个相邻节点的对数时间更新它在优先级队列中的位置（大多数实现优先级队列）。v v

为了命名一些特定的数据结构，DecreaseKey(Q, v)下面使用的函数对斐波那契堆和配对堆（摊销）具有对数复杂度。

算法的更具体的伪代码

MstPrim(Graph* G)
    for each u in G->vertices
        u->visited = false
        u->key = infinity
        u->pi = NULL
    Q = PriorityQueue(G->vertices)
    while Q not empty
        u = ExtractMin(Q)
        u->visited = true
        for each (v, w) in u->adjacent
            if not v->visited and w < v->key
                v->pi = u
                v->key = w
                DecreasedKey(Q, v) //O(log n)
于 2013-06-12T22:23:55.277 回答