algorithm - 普里姆算法 : How to get index of key on which DECREASE_KEY operation is to be performed?

Question

所以我遵循这个 Prim 的 MST 算法

输入:邻接表形式的图G(V,E)

1. 使用构建堆时间复杂度为顶点创建一个最小堆:O(V)
2. 重复以下步骤，直到堆中没有更多元素。
3. 在堆上调用 extract-min 以最小成本 O(log V) 获取顶点
4. 对于提取的顶点，在邻接表中找到相邻的顶点。
5. 对堆中的相邻顶点执行减少键操作。 O(登录V)

我类给出的算法的时间复杂度分析是这样的:

O(V) => to build heap
O(VlogV) => V times EXTRACT_MIN operation
2E => traverse all edges in adjacency list
ElogV => E times DECREASE_KEY operation (Worst Case)

EXTRACT_MIN => O(logV)
DECREASE_KEY => O(logV)

Total Time Complexity = V + V*logV + 2E + E*log V
                      = O((V+E) logV)

我的问题是在执行decease key操作之前不需要在min heap中找到相应的元素吗？并且在堆中搜索元素将花费 O(V) 时间。

对于上面的图表，我会做这样的事情(使用数组实现的最小堆)

                      A    B    C    D   E   F
                    ----------------------------------
 chosen as min        0   INF  INF  INF INF INF  ------> cost associated with vertices
                    ------------------------------
 A                        7    2    6   INF INF
                     ------------------------------
 C                        6         6    8   5
                     ------------------------------
 F                        6         3    7
                     ------------------------------
 D                        6              7
                     ------------------------------
 B                                       4
                     ------------------------------
 E

我的数组(最小堆)最初看起来像这样:每个元素由两部分组成:顶点名称，成本。最小堆基于成本。

 A,0 | B,INF | C,INF | D,INF | E,INF | F,INF

现在在获得第一个最小元素 (A) 之后，我在邻接列表中寻找它的相邻顶点并找到B、C和D。现在我需要对最小堆中的这些顶点执行减少键操作。

只有当我知道要执行减少键操作的顶点的索引时，DECREASE_KEY 操作才会起作用。要获取索引，我是否需要先在数组中搜索它并花费 O(V) 的额外时间？

Answer 1

好吧，您可以按照自己的方式解决这个问题。它需要保持指针从每个顶点返回到它在堆中的索引。每当堆中的元素被交换时，两个关联顶点上的指针就会被调整。然后当你需要调整一个顶点的键时，你可以跟随指针回到它在堆中的索引。

但是，我通常不会那样做...

我通常将 (cost,vertex) 记录放在堆中，每当顶点的成本下降时，我就放入一个新的。当我从堆中弹出一个顶点时，如果它已经完成，我就忽略它。无论如何，您必须跟踪完成了哪些顶点，所以这很容易。

这需要 O(|E|) 空间而不是 O(|V|)，但这通常不是什么大问题，时间复杂度保持不变。