Prim 算法：如何获取要执行 DECREASE_KEY 操作的键的索引？
Prim's Algorithm: How to get index of key on which DECREASE_KEY operation is to be performed?
所以我正在为 Prim 的 MST 遵循这个算法
输入：邻接表形式的图G(V,E)
- 使用构建堆时间复杂度为顶点创建最小堆：O(V)
- 重复以下步骤，直到堆中没有更多元素。
- 在堆上调用 extract-min 以最小成本 O(log V) 获取顶点
- 对于提取的顶点，在邻接列表中找到相邻的顶点。
- 对堆中的相邻顶点执行减键操作。 O(logn V)
我的 class 中给出的算法的时间复杂度分析是这样的：
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操作之前不需要在最小堆中找到对应的元素吗？并且在堆中搜索元素将花费 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) 的额外时间？
好吧，你可以按你想要的方式解决这个问题。它需要保持指针从每个顶点返回到它在堆中的索引。每当堆中的元素被交换时，两个关联顶点上的指针就会被调整。然后当你需要调整一个顶点的键时，你可以跟随指针回到它在堆中的索引。
不过，我一般不会那样做...
我通常将 (cost,vertex) 记录放在堆中，每当顶点的成本下降时，我就放入一个新的。当我从堆中弹出一个顶点时，如果它已经完成，我就忽略它。无论如何，您必须跟踪完成了哪些顶点，所以这很容易。
这需要 O(|E|) space 而不是 O(|V|)，但这通常不是什么大问题，时间复杂度保持不变。
所以我正在为 Prim 的 MST 遵循这个算法
输入：邻接表形式的图G(V,E)
- 使用构建堆时间复杂度为顶点创建最小堆：O(V)
- 重复以下步骤，直到堆中没有更多元素。
- 在堆上调用 extract-min 以最小成本 O(log V) 获取顶点
- 对于提取的顶点，在邻接列表中找到相邻的顶点。
- 对堆中的相邻顶点执行减键操作。 O(logn V)
我的 class 中给出的算法的时间复杂度分析是这样的：
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操作之前不需要在最小堆中找到对应的元素吗？并且在堆中搜索元素将花费 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) 的额外时间？
好吧，你可以按你想要的方式解决这个问题。它需要保持指针从每个顶点返回到它在堆中的索引。每当堆中的元素被交换时，两个关联顶点上的指针就会被调整。然后当你需要调整一个顶点的键时，你可以跟随指针回到它在堆中的索引。
不过，我一般不会那样做...
我通常将 (cost,vertex) 记录放在堆中，每当顶点的成本下降时，我就放入一个新的。当我从堆中弹出一个顶点时，如果它已经完成，我就忽略它。无论如何，您必须跟踪完成了哪些顶点，所以这很容易。
这需要 O(|E|) space 而不是 O(|V|)，但这通常不是什么大问题，时间复杂度保持不变。