第45章：Prim的算法进阶

挑战1：点的最小生成树

给出一组点，构建一个连接所有点的最小生成树，成为一个图。

挑战2：关于X你能说什么？

考虑到下面的图和最小生成树，你能对X的值说些什么？

挑战3：分步图

给出下图，通过Prim的算法产生最小生成树，并提供总成本。从顶点B开始。如果两条边的权重相同，按字母顺序排列。

解决方案

挑战1的解决方案

你可以把这些点看作是图上的顶点。要用这些点构建最小生成树，首先需要知道每两个点之间的加权边。

顶点要求其元素是可哈希的。Starter项目提供了对CGPoint的扩展。

extension CGPoint: Hashable { 
  public func hash(into hasher: inout Hasher) { 
    hasher.combine(x) 
    hasher.combine(y) 
  } 
}

每个顶点都有一个相关的CGPoint。为了形成一条通往另一个顶点（CGPoint）的边，你需要计算点之间的距离。

在下面添加以下代码。

• distanceSquared(_:) 通过添加对边和邻边的平方距离来计算斜边的平方值。

• distance(_:) 通过取距离平方的平方根来返回斜边。

现在你已经建立了一种计算两点之间距离的方法，你已经拥有了形成最小生成树的所有必要信息

回顾一下。在上一章中，你学会了如何构建一棵最小生成树。你通过挑选一个任意的顶点，并贪婪地挑选到其相邻顶点的最便宜的边，直到有一条边连接所有的顶点。

为了利用Prim的算法，你必须用给定的点集形成一个完整的图。一个完整的图是一个无向图，其中有一条唯一的边连接着所有的顶点对。想象一下一个有五个顶点的五边形。每个顶点都与其他每个顶点相连，形成一个星形!

添加以下代码。

这里你创建了一个扩展，作为Prim的一部分，并检查元素是否为CGPoint类型。

1. 创建一个空的新图形。

2. 穿过每个点并创建一个顶点。

3. 循环浏览每个顶点和其他每个顶点，只要这两个顶点不相同。

4. 计算两个顶点之间的距离。

5. 在这两个顶点之间添加一条有向边。

6. 返回完整的图形

现在你可以使用给定的点形成一个完整的图，并利用prim的算法来形成最小生成树。在createCompleteGraph(_:)之后添加以下内容。

下面是一个样本数据集，显示了最小生成树是如何形成的。

挑战2的解决方案

x的值小于或等于5。

挑战3的解决方案

Edges [A:2, D:8, C:6, E:2] 
Edges part of MST: [A:2] 
Explored [A, B]

Edges [D:8, C:6, E:2, D:3, C:21] 
Edges part of MST: [A:2, E:2] 
Explored [A, B, E]

Edges [D:8, C:6, D:3, C:21, D:12, C:4] 
Edges part of MST: [A:2, E:2, D:3] 
Explored [A, B, E, D]

Edges [C:6, C:21, C:4] 
Edges part of MST: [A:2, E:2, D:3, C:4] 
Explored [A, B, E, D, C]

Edges [A:2, E:2, D:3, C:4] 
Explored [A, B, E, D, C] 
Total Cost: 11

---

上一章	目录	首页