44.`Prim`的算法¶

在前几章中，你已经看过深度优先和广度优先的搜索算法了。这些算法形成了spanning trees。

spanning trees是无向图的一个子图，包含图的所有顶点，用最少的边连接。一个生成树不能包含一个周期，也不能断开连接。

下面是一个图G和它所有可能的生成树：

从这个形成三角形的无向图中，你可以生成三种不同的生成树，其中你只需要两条边来连接所有顶点。

本章将介绍Prim’s algorithm，这是一种用于构建minimum spanning tree的贪婪算法。贪婪算法是逐步构建一个解决方案，并在每一步中孤立地选择最优化的路径。

最小生成树可以使被选择来跨越该树的边的总重量最小化。它在各种情况下都有帮助。例如，你可能想找到最便宜的方式来布局水管网络。

下面是一个加权无向图的最小生成树的例子：

Note

只有第三个子图形成了最小生成树，因为它的总成本是3。

Prim的算法通过一次选择一条边来创建最小生成树。它是贪婪的，因为每次选择边时，都是选择连接一对顶点的最小的加权边。

用Prim的算法寻找最小生成树有六个步骤：

例子¶

想象一下，下面的图表示一个机场网络。顶点是机场，边表示飞机从一个机场飞到另一个机场的燃料成本。

让我们开始通过这个例子工作：

在图中选择任何一个顶点。让我们假设你选择了vertex 2。
这个顶点的边的权重为[6, 5, 3]。一个贪婪的算法会选择权重最小的边。
选择权重为3并与vertex 5相连的边。

探索的顶点是{2，5}。
从已探索的顶点中选择下一条最短的边。这些边是[6，5，6，6]。你选择权重为5的边，它与vertex 3相连。
注意vertex 5和vertex 3之间的边可以从考虑中删除，因为它已经是生成树的一部分。

探索的顶点是{2，3，5}。
接下来的潜在边是[6, 1, 5, 4, 6]。你选择权重为1的边，它与vertex 1相连。
vertex 2和vertex 1之间的边可以被删除。

探索的顶点是{2, 3, 5, 1}。
从已探索的顶点中选择下一条最短的边。这些边是[5, 5, 4, 6]。你选择权重为4的边，它与vertex 6相连。
可以删除vertex 5和vertex 6之间的边。

探索的顶点是{2, 5, 3, 1, 6}。
从已探索的顶点中选择下一条最短的边。这些边是[5, 5, 2]。你选择权重为2的边，它与vertex 4相连。
从vertex 1和vertex 3连接到vertex 4的边[5, 5]可以被删除。

Note

如果所有的边都有相同的权重，你可以选择其中任何一条。

这张最后的图是我们的例子中由Prim算法产生的最小生成树。

接下来，让我们看看如何在代码中建立这个模型。

实施¶

打开本章的入门playground。这个playground上有一个邻接列表图和一个优先级队列，你将用它们来实现Prim的算法。

优先级队列用于存储探索过的顶点的边。它是一个最小优先级队列，所以每次当你取消一个边时，它都会给你一个权重最小的边。

首先定义一个Prim类。打开Prim.swift并添加以下内容：

public class Prim<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  public init() {}
}

Graph被定义为AdjacencyList的类型别名。在未来，如果需要的话，你可以用一个邻接矩阵来代替它。

帮助方法¶

在构建算法之前, 你将创建一些辅助方法来保持你的组织性并合并重复的代码.

复制一个图¶

要创建一个最小生成树，你必须包括原图的所有顶点。打开AdjacencyList.swift，在AdjacencyList类中添加以下内容：

public func copyVertices(from graph: AdjacencyList) {
  for vertex in graph.vertices {
    adjacencies[vertex] = []
  }
}

这就把一个图的所有顶点复制到一个新的图中。

寻找边沿¶

除了复制图形的顶点，你还需要找到并存储你探索的每个顶点的边。打开Prim.swift，在Prim类中添加以下内容：

internal func addAvailableEdges(
    for vertex: Vertex<T>,
    in graph: Graph,
    check visited: Set<Vertex<T>>,
    to priorityQueue: inout PriorityQueue<Edge<T>>) {
  for edge in graph.edges(from: vertex) { // 1
    if !visited.contains(edge.destination) { // 2
      priorityQueue.enqueue(edge) // 3
    }
  }
}

这个方法需要四个参数：

当前的vertex。
graph，当前的vertex被存储在其中。
已经访问过的顶点。
增加所有潜在边的优先队列。

在该函数中，你要做以下工作：

查看与当前vertex相邻的每一条边。
检查destination顶点是否已经被访问过。
如果它没有被访问过，你就把这条边添加到优先级队列中。

现在你已经建立了辅助方法，你可以实现Prim的算法。

生成最小生成树¶

在类Prim中添加以下方法：

public func produceMinimumSpanningTree(for graph: Graph)
    -> (cost: Double, mst: Graph) { // 1
  var cost = 0.0 // 2
  let mst = Graph() // 3
  var visited: Set<Vertex<T>> = [] // 4
  var priorityQueue = PriorityQueue<Edge<T>>(sort: { // 5
    $0.weight ?? 0.0 < $1.weight ?? 0.0
  })
  // to be continued
}

以下是你目前的情况：

produceMinimumSpanningTree接收一个无向图，并返回一个最小生成树和它的成本。
cost记录最小生成树中的边的总重量。
这是一个图，将成为你的最小生成树。
visited存储所有已经被访问过的顶点。
这是一个最小优先级的队列，用来存储边。

接下来，继续实现produceMinimumSpanningTree，内容如下：

mst.copyVertices(from: graph) // 1

guard let start = graph.vertices.first else { // 2
  return (cost: cost, mst: mst)
}

visited.insert(start) // 3
addAvailableEdges(for: start, // 4
                   in: graph,
                check: visited,
                   to: &priorityQueue)

// to be continued

这段代码启动了该算法：

将原图中的所有顶点复制到最小生成树上。
从图中获取起始顶点。
将起始顶点标记为已访问。
将所有可能的边从start顶点添加到优先级队列中。

最后，用以下方法完成produceMinimumSpanningTree：

while let smallestEdge = priorityQueue.dequeue() { // 1
  let vertex = smallestEdge.destination // 2
  guard !visited.contains(vertex) else { // 3
    continue
  }

  visited.insert(vertex) // 4
  cost += smallestEdge.weight ?? 0.0 // 5

  mst.add(.undirected, // 6
          from: smallestEdge.source,
          to: smallestEdge.destination,
          weight: smallestEdge.weight)

  addAvailableEdges(for: vertex, // 7
                    in: graph,
                    check: visited,
                    to: &priorityQueue)
}

return (cost: cost, mst: mst) // 8

翻阅代码：

继续Prim的算法，直到边的队列为空。
获取destination顶点。
如果这个顶点已经被访问过，重新开始循环，得到下一个最小的边。
将destination顶点标记为已访问。
将边的weight加到总cost中。
将最小的边加入你正在构建的最小生成树中。
添加来自当前顶点的可用边。
一旦priorityQueue为空，返回最小成本和最小生成树。

测试你的代码¶

导航到主playground，你会看到上面的图已经用邻接表构建好了。

现在是时候看看Prim的算法的作用了。添加以下代码：

let (cost,mst) = Prim().produceMinimumSpanningTree(for: graph)
print("cost: \(cost)")
print("mst:")
print(mst)

这段代码从例子部分构建了一个图。你会看到下面的输出：

cost: 15.0
mst:
5 ---> [ 2 ]
6 ---> [ 3, 4 ]
3 ---> [ 2, 1, 6 ]
1 ---> [ 3 ]
2 ---> [ 5, 3 ]
4 ---> [ 6 ]

性能¶

在上面的算法中，你维护了三个数据结构：

一个建立最小生成树的邻接列表图。将顶点和边添加到邻接列表中是O(1)。
一个Set来存储所有你访问过的顶点。向集合中添加顶点和检查集合是否包含顶点的时间复杂性也是O(1)。
一个最小优先级队列，在你探索更多顶点时存储边。优先级队列建立在一个堆上，插入需要`O(log E)。

Prim算法的最坏情况下的时间复杂度是O(E log E)。每次从优先级队列中提取最小的边时，必须遍历destination顶点的所有边(O(E))，并将该边插入优先级队列(O(logE))。

关键点¶

生成树是无定向图的一个子图，包含所有边数最少的顶点。
Prim的算法是一种贪婪的算法，它构建了一个minimum spanning tree，在算法的每一步都使每条边的权重最小。
为了实现Prim的算法，你可以利用三种不同的数据结构：优先级队列、集合和邻接列表。

44.Prim的算法¶

例子¶

实施¶