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. LetT
be any MST and let(U, V \ U)
be any cut. ThenT
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
.