Prim的MST算法问题的时间复杂度

Time complexity of Prim's MST algorithm problem

我有一个图表问题:

  1. 恰好有 n 个顶点和 n-1 条边。
  2. 所有顶点都相互连接——即网络由 只有一个连接的组件。因此网络是一棵树。
  3. 所有边的长度都是正数(严格大于 0)。所有边缘都可以携带 双向交通。
  4. 我给出了每对顶点之间的最短路径距离。

更正式地说:让实际的顶点网络是一棵树T。鉴于只是 T的最短路径距离,需要重构原网络T.

输入:一个n×n距离矩阵H Hi,j = δT (i,j),其中T是实际的 网络的顶点和 δT 是之间的最短路径距离 在 T.

中的顶点 ij

输出T.

n −1条边

示例:

•T是实际的顶点网络。

•H是n×n最短路径距离矩阵。

•G(H)是n个节点上的完全图,其中边(i,j)的权重为Hi,j – 即 T 中的最短路径距离。

我关于时间复杂度的问题:

运行 算法的 运行 时间是多少,由 运行 Prim 算法对输入产生并作为函数返回边列表 n? (注意 |E(G(H))|= Θ(n2))。应在此处使用摊销分析吗?我不太确定。

Prim算法使用完全图的邻接矩阵的时间复杂度为Theta(n^2)。我们可以从带有邻接矩阵 H:

的 Prim 算法的伪代码中看出这一点
  1. 初始化一组 Q 不在树中的顶点,最初是所有顶点。选择第一个顶点作为我们的根 R.
  2. 初始化两个长度为nkeyparent的数组。 key 将在位置 i 处存储连接第 i 个顶点和当前 MST 的最小权重边;最初,这是 +infinity。 parent 将在算法完成后存储以 R 为根的 MST 中每个顶点的父节点。最初,parent[i] = R 代表所有 i,除了没有父代的根。
  3. 循环H的第一行(对应根R)并赋值key[i] = H[0][i]。从我们的集合 Q.
  4. 中删除 R
  5. 虽然 Q 不为空:
    • 遍历 Q,并提取具有最小 key[u]
    • 的任何顶点 u
    • 对于从 0 到 n-1 的每个顶点 v
      • 如果 vQH[u][v] < key[v] 中:
        • 设置key[v] = H[u][v]
        • 设置parent[v] = u

这里,(4) 中的循环运行了 n-1 次,在循环内部,我们做了 Theta(n) 次工作。总的来说,这给出了 Theta(n^2) 的运行时间,这对于需要读取整个邻接矩阵的任何算法都是最佳的。特别是,对于通用的完整图,这是最优的,但这并不意味着 Prim 的算法对于您的特定情况是最优的,因为距离矩阵形成的图较窄 class。


为了证明你的问题变换是正确的,我们需要验证,给定一棵权重为正的树T,由[=44]的距离矩阵形成的完整图G(H) =]作为邻接矩阵将满足:

  1. G(H)有唯一的最小生成树
  2. TG(H)的最小生成树。

这需要证明一般最小生成树的几个性质。关于最小生成树的一个定理,在 these MIT lecture notes 中被证明为推论 3.5,它说:

Let G = (V,E,w) be a connected, weighted, undirected graph. Let T be any MST and let (U, V \ U) be any cut. Then T contains a light edge for the cut.

这里,'light edge for a cut (U, V \ U)'表示一条边,其权重是U中恰好有一个端点的所有边中权重最小的边。

现在,我们只需要选择合适的剪辑来证明我们想要的。对于原始树 T 中的任意边 e,考虑通过删除 e.

得到的两棵树 T1T2

T1 的顶点作为我们的切割,我们称之为 V(T1)。我们需要证明在完整的图形 G(H) 中,边 e 是该切割的唯一轻边。在我们原来的树 T 中,e 是唯一穿过切口的边。这意味着在 V(T1) 中具有一个端点 u 且在 V(T2) 中具有另一个端点 v 的任何路径都必须包含 e.

由于所有权重都是正数,这意味着对于任何 u, v such that (u in V(T1), v in V(T2), and (u, v) != e),T 中的距离 distance(u,v) > weight(e)。由于 uv 之间的 T 中的距离是我们完整图 G(H) 中边 (u, v) 的权重,这意味着 e是穿过切口的唯一最小权重边。由于 eT 中的任意边,这意味着 T 的所有边都必须在我们 G(H) 的 MST 中,因此 [=45= 的唯一 MST ] 是 T.