prim的MST算法的邻接矩阵复杂度和邻接表线性搜索的复杂度一样吗？
Is the complexity of prim's MST algorithm by adjacency matrix same as that of adjacency list with linear search?
根据我的理解，每次更改值时，堆的使用有助于通过 log n 的额外工作找到最小值的恒定成本。值的变化最多可以发生 e 次。时间复杂度约为O(e) + O(e log n) = O(e log n)。
如果是稠密图，e = n^2。
但是，如果我们在 value array 上使用线性搜索来搜索最小值，我们将得到 O(e) + O(n^2) = O(n^2) 的复杂度，这对于密集图来说优于 elog n。这类似于我们在 prim 的 MST 算法中使用二维数组进行图形表示所得到的结果。
那为什么我们要为这个特定的算法使用二维数组表示呢？
e = 边数。
n = 节点数。
你是对的；在密集图上为 Prim 使用花哨的堆数据结构是没有意义的。不过，Prim 的定义特征与其说是堆，不如说是尽可能便宜地重复扩展部分 MST 的想法。
邻接矩阵的点是出于 space（无指针开销）和架构原因（顺序访问通常比随机访问更有效）。
根据我的理解，每次更改值时，堆的使用有助于通过 log n 的额外工作找到最小值的恒定成本。值的变化最多可以发生 e 次。时间复杂度约为O(e) + O(e log n) = O(e log n)。
如果是稠密图，e = n^2。
但是，如果我们在 value array 上使用线性搜索来搜索最小值，我们将得到 O(e) + O(n^2) = O(n^2) 的复杂度，这对于密集图来说优于 elog n。这类似于我们在 prim 的 MST 算法中使用二维数组进行图形表示所得到的结果。
那为什么我们要为这个特定的算法使用二维数组表示呢？
e = 边数。
n = 节点数。
你是对的；在密集图上为 Prim 使用花哨的堆数据结构是没有意义的。不过，Prim 的定义特征与其说是堆，不如说是尽可能便宜地重复扩展部分 MST 的想法。
邻接矩阵的点是出于 space（无指针开销）和架构原因（顺序访问通常比随机访问更有效）。