令 G = (V, E) 为加权、连通且无向图。让 T1 和 T2 是 2 个不同的 MST。假设我们可以写 E = (A1 UBU A2) 使得：
B 是 T1 和 T2 的边的交点，并且
A1 = T1 - B
A2 = T2 - B
假设 G 中的每一个 MST T 都包含 B 的所有边，找到一个算法来判断是否存在一个 MST T 包含 A1 中的至少一条边和 A2 中的至少一条边。
编辑：我已经放弃了这里的部分。我认为它弊大于利。
问问题
310 次
1 回答
1
你应该对你的边缘进行排序，红色边缘比蓝色边缘更适合选择。然后你可以使用任何与Prim算法相同的 MST 算法：
如果图表为空，那么我们立即完成。因此，我们假设并非如此。该算法从一棵由单个顶点组成的树开始，并不断增加它的大小，一次增加一条边，直到它跨越所有顶点。输入：具有顶点 V 和边 E 的非空连接加权图（权重可以为负）。初始化：Vnew = {x}，其中 x 是 V 的任意节点（起点），Enew = {} 重复直到 Vnew = V：选择具有最小权重的边 {u, v}，使得 u 在 Vnew 和 v不是（如果有多个具有相同权重的边，可以选择其中任何一个）将 v 添加到 Vnew，并将 {u, v} 添加到 Enew 输出：Vnew 和 Enew 描述了一个最小生成树
于 2013-04-27T20:52:02.823 回答