45.`Prim`的算法挑战¶

挑战1：点的最小生成树¶

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

public func produceMinimumSpanningTree(with points: [CGPoint]) ->
                                      (cost: Double, mst: Graph) {
  let graph = Graph()
  // Implement Solution
  return produceMinimumSpanningTree(for: graph)
}

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

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

挑战3：分步示意图¶

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

解决方案¶

挑战1的解决方案¶

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

一个Vertex要求其元素是Hashable的。启动项目提供了对CGPoint的扩展：

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

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

在下面添加以下代码：

extension CGPoint {
  func distanceSquared(to point: CGPoint) -> CGFloat {
    let xDistance = (x - point.x)
    let yDistance = (y - point.y)
    return xDistance * xDistance + yDistance * yDistance
  }

  func distance(to point: CGPoint) -> CGFloat {
    distanceSquared(to: point).squareRoot()
  }
}

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

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

Recall

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

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

添加以下代码：

extension Prim where T == CGPoint {

  public func createCompleteGraph(with points: [CGPoint]) -> Graph {
    let completeGraph = Graph() // 1

    points.forEach { point in // 2
      completeGraph.createVertex(data: point)
    }

    // 3
    completeGraph.vertices.forEach { currentVertex in
      completeGraph.vertices.forEach { vertex in
        if currentVertex != vertex {
          let distance = Double(currentVertex.data.distance(to: vertex.data)) // 4
          completeGraph.addDirectedEdge(from: currentVertex,
                                        to: vertex,
                                        weight: distance) // 5
        }
      }
    }

    return completeGraph // 6
  }
}

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

创建一个空的新图。
遍历每个点并创建一个顶点。
循环浏览每个顶点和其他每个顶点，只要这两个顶点不相同。
计算两个顶点之间的距离。
在这两个顶点之间添加一条有向边。
返回完整的图形。

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

public func produceMinimumSpanningTree(with points: [CGPoint]) ->
                                      (cost: Double, mst: Graph) {
  let completeGraph = createCompleteGraph(with: points)
  return produceMinimumSpanningTree(for: completeGraph)
}

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

挑战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

45.Prim的算法挑战¶