0

图形

所以我需要解决这个图表，我对如何解决它有一个大致的想法，但如果我做错了，请纠正我。

所以要找到 MST 我需要在图上执行 Kruskals 算法

这是我的这个 Kruskals 算法的伪代码

克鲁斯卡尔(V,E) A = null; 对于每个 v 包含在 V 中，使不相交集 (v) 按权重对 E 进行排序，对于每个 (v1, v2) 包含在 E 中，如果

  克鲁斯卡尔(V,E)



一个=空；
对于每个 v 包含在 V
     制作不相交集(v)
越来越多地按权重对 E 进行排序
对于每个（v1，v2）包含在 E
     如果 Find(v1) 不等于 Find(v2)
          A = 联合 {(v1,v2)}
          联合（v1，v2）
返回 A

所以我要做的第一件事就是找到距离最短的节点，对吧？

1)

我假设 S 到 H 的距离最短，因为 d(h,s) = -3

所以 A = {(h,s)}

所以现在我们遵循这个模式

2) A = {(h,s),(s,f)}

3) A = {(h,s),(s,f)(s,n)}

4) A = {(h,s)(s,f)(s,n)(f,k)}

5) A = {(h,s)(s,f)(s,n)(f,k)(s,m)} （我们跳过 H 到 N 因为一条从 h 到 n 的路径已经通过s)

6) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

所以现在既然有一条连接到所有边缘的路径，我们就很好了，对吧？

但我不明白的是有距离[u，v]比通过多个顶点的路径[u，v]短。例如 d[d,m] 比 p[d,m] 先通过 B 短。难道我做错了什么？

4

1 回答 1

1

你没有做错什么。不能保证 MST 保留节点之间的最短距离。例如：边权重为 3、2、2 的三节点完整图 ABC（为我的 ascii 艺术道歉）：

A --- 2 --- B
|           |
2          /
|         /
C----3---/

最小生成树是 CAB，但原始图中 B 和 C 之间的距离是 3，而在 MST 中是 4。

于 2015-04-26T03:00:12.607 回答