algorithm - 使用数组的 Prims 的复杂性

Question

使用数组和邻接表的Prims算法的复杂度为:

V^2 + V + 2E + E = O(V^2)

但是，我不记得为什么 E。

Answer 1

使用邻接表结构表示图和使用数组表示优先级队列的复杂度为Θ(|V|² + |E|)。对于没有平行边的图，这是 Θ(|V|²)。

Prim 的算法在 |V| 次迭代中工作，从大小 1 开始生长一棵树，以大小 |V| 结束。假设在某些迭代中，顶点 v 被添加到树中，并且让 E(v) 成为从 v 发出的边。对于每条这样的边，我们可以找到数组中的邻居，并更新从当前树中某个顶点到它的最轻距离。找到顶点 v 需要时间 Θ(|V|)，因为我们必须扫描数组以找到最小值(这是优先级队列的低效实现)。 p>

总而言之，每个边在每个方向上被访问一次(因此 Θ(|E|)，并且每个 |V| 迭代执行一个 Θ (|V|) 扫描阵列。

---

请注意，对于问题中的表达式，V^2+V+2E+E，重要的是要记住上下文是对增长顺序的考虑。因此 2E 没有太多意义(2 代表什么？在边上迭代两次？每个边的 CPU 指令数？)或者 2E + E .这些只是模糊的速记符号，有时用于指示算法中的各个阶段。