Prim的MST算法问题的时间复杂度
Time complexity of Prim's MST algorithm problem
我有一个图表问题：
- 恰好有 n 个顶点和 n-1 条边。
- 所有顶点都相互连接——即网络由
只有一个连接的组件。因此网络是一棵树。
- 所有边的长度都是正数（严格大于 0）。所有边缘都可以携带
双向交通。
- 我给出了每对顶点之间的最短路径距离。
更正式地说：让实际的顶点网络是一棵树T。鉴于只是
T的最短路径距离，需要重构原网络T.
输入：一个n×n距离矩阵H与 Hi,j = δT (i,j)，其中T是实际的
网络的顶点和 δT 是之间的最短路径距离
在 T.
中的顶点 i 和 j
输出：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 算法的伪代码中看出这一点
- 初始化一组
Q 不在树中的顶点，最初是所有顶点。选择第一个顶点作为我们的根 R.
- 初始化两个长度为
n、key和parent的数组。 key 将在位置 i 处存储连接第 i 个顶点和当前 MST 的最小权重边；最初，这是 +infinity。 parent 将在算法完成后存储以 R 为根的 MST 中每个顶点的父节点。最初，parent[i] = R 代表所有 i，除了没有父代的根。
- 循环
H的第一行（对应根R）并赋值key[i] = H[0][i]。从我们的集合 Q. 中删除 R
- 虽然
Q 不为空：
- 遍历
Q，并提取具有最小 key[u] 的任何顶点 u
- 对于从 0 到 n-1 的每个顶点
v：
- 如果
v 在 Q 和 H[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) =]作为邻接矩阵将满足：
G(H)有唯一的最小生成树T是G(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.
得到的两棵树 T1 和 T2
将 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)。由于 u 和 v 之间的 T 中的距离是我们完整图 G(H) 中边 (u, v) 的权重，这意味着 e是穿过切口的唯一最小权重边。由于 e 是 T 中的任意边，这意味着 T 的所有边都必须在我们 G(H) 的 MST 中，因此 [=45= 的唯一 MST ] 是 T.
我有一个图表问题：
- 恰好有 n 个顶点和 n-1 条边。
- 所有顶点都相互连接——即网络由 只有一个连接的组件。因此网络是一棵树。
- 所有边的长度都是正数（严格大于 0）。所有边缘都可以携带 双向交通。
- 我给出了每对顶点之间的最短路径距离。
更正式地说：让实际的顶点网络是一棵树T。鉴于只是 T的最短路径距离，需要重构原网络T.
输入：一个n×n距离矩阵H与 Hi,j = δT (i,j)，其中T是实际的 网络的顶点和 δT 是之间的最短路径距离 在 T.
中的顶点 i 和 j输出：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:
- 初始化一组
Q不在树中的顶点，最初是所有顶点。选择第一个顶点作为我们的根R. - 初始化两个长度为
n、key和parent的数组。key将在位置i处存储连接第i个顶点和当前 MST 的最小权重边；最初，这是 +infinity。parent将在算法完成后存储以R为根的 MST 中每个顶点的父节点。最初，parent[i] = R代表所有i，除了没有父代的根。 - 循环
H的第一行（对应根R）并赋值key[i] = H[0][i]。从我们的集合Q. 中删除 - 虽然
Q不为空：- 遍历
Q，并提取具有最小key[u] 的任何顶点 - 对于从 0 到 n-1 的每个顶点
v：- 如果
v在Q和H[u][v] < key[v]中：- 设置
key[v]=H[u][v] - 设置
parent[v]=u
- 设置
- 如果
u - 遍历
R
这里，(4) 中的循环运行了 n-1 次，在循环内部，我们做了 Theta(n) 次工作。总的来说，这给出了 Theta(n^2) 的运行时间，这对于需要读取整个邻接矩阵的任何算法都是最佳的。特别是，对于通用的完整图，这是最优的，但这并不意味着 Prim 的算法对于您的特定情况是最优的，因为距离矩阵形成的图较窄 class。
为了证明你的问题变换是正确的，我们需要验证，给定一棵权重为正的树T，由[=44]的距离矩阵形成的完整图G(H) =]作为邻接矩阵将满足：
G(H)有唯一的最小生成树T是G(H)的最小生成树。
这需要证明一般最小生成树的几个性质。关于最小生成树的一个定理，在 these MIT lecture notes 中被证明为推论 3.5，它说：
Let
G = (V,E,w)be a connected, weighted, undirected graph. LetTbe any MST and let(U, V \ U)be any cut. ThenTcontains a light edge for the cut.
这里，'light edge for a cut (U, V \ U)'表示一条边，其权重是U中恰好有一个端点的所有边中权重最小的边。
现在，我们只需要选择合适的剪辑来证明我们想要的。对于原始树 T 中的任意边 e，考虑通过删除 e.
T1 和 T2
将 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)。由于 u 和 v 之间的 T 中的距离是我们完整图 G(H) 中边 (u, v) 的权重，这意味着 e是穿过切口的唯一最小权重边。由于 e 是 T 中的任意边，这意味着 T 的所有边都必须在我们 G(H) 的 MST 中，因此 [=45= 的唯一 MST ] 是 T.