在之前的文章里，我们共同探讨了广度优先搜索算法和深度优先搜索算法，这些算法构成了生成树。
生成树是无向图的一个子图，包含图的所有顶点，并且使用最小数量的边。它不能包含一个环，其不能不相连。
下图是一些生成树的示例：
Prim1.png
从这个无向图中，可以得到3个不同的生成树，只需要两条边就可以连接所有的点。
在这篇文章中，我们将探索 Prim算法，一个贪婪算法，经常使用它来构建 最小生成树。
最小生成树是一个总的边的权值最小的生成树。举个例子，你可以使用它找到铺设水管时的最短路径。
下图是一个有权的无向图的最小生成树：
Prim2.png
注意只有第三个子图是最小生成树，因为它的总花费最少为3。
Prim算法是通过每次都选择权值最小的边来生成最小生成树的，下面的图通过6步，就可以得到最小生成树。
Prim3.png
示例
将下图想象成一个机场的航线图。图中顶点是机场，图中的边表示该航线从一个机场到另一个机场所花费的油费。
Prim4.png
我们从该图开始分析：
Prim5.png
1，选择图中任意一个顶点，在这里我们选择顶点2。
2，这个顶点的边的权重为[6,5,3]。贪婪算法选择权值最小的边。
3，选择权重为3的边，并且将它和顶点5连接。
Prim6.png
1，已经访问的顶点是{2,5}
2，从已访问顶点的所有边中，选择一个最小的边。所有的边是{6,5,6,6},我们选择权重为5的边，它和顶点3相连。
3，这里需要注意的是 顶点5和顶点3之间的边可以移除了，顶点{2, 3, 5}现在已经是生成树的一部分。
Prim7.png
1，现在已访问的顶点是{2, 3, 5}。
2，现在潜在的边的是{6, 1, 5, 4, 6}，我们选择连接顶点1，权重为顶点1的边。
3，顶点2和顶点1之间的边现在可以移除掉了。
Prim8.png
1，已访问的顶点是{2,3,5,1}
2，在[5,5,4,6]中选择最短的边，此时，我们选择连接顶点6权重为4的边。
3，移除顶点5 和 顶点6 之间的边。
Prim10.png
1，现在已访问的顶点是 {2,5,3,1,6}。
2，在与已访问顶点的边中选择最短的边。现在相关的边是[5, 5, 2]。
3，删除连接顶点4与顶点1，顶点6的边。
⚠️如果所有的边有相同的权重值，我们可以从中任意选择一个。
Prim11.png
上图就是我们使用 Prim算法得到的最小生成树。
实现
我们先添加如下代码：
public class Prim<T: Hashable> {
public typealias Graph = AdjacencyList<T>
public init() {}
}
将Graph定义为 AdjacencyList的别名。
辅助方法
在开始实现该算法之前，我们来创建一个辅助方法，避免重复的代码。
复制图
public func copyVertices(from graph: AdjacencyList) {
for vertex in graph.vertices {
adjacencies[vertex] = []
}
}
把邻接表中所有的顶点复制到新的邻接表中
查找边
除了复制图中所有的顶点之外，我们需要查找并存储已经访问过的顶点所相关的边。
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
}
}
}
这个方法包含4个参数：
1，当前的顶点。
2，graph 用来存储当前顶点。
3，已经访问的顶点。
4，优先级队列来存放潜在的边。
该方法做了以下事情：
1，查找和当前顶点相关联的边。
2，检查 目的顶点是否已经被访问过。
3，如果没有被访问过，就把它加到优先级队列中。
创造最小生成树
在 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
}
1，produceMinimumSpanningTree方法将 无向图作为参数，并且返回一个包含最小生成树和其总权重的元组。
2，cost用来记录最小生成树总的权重。
3，这个图将会变为最小生成树。
4，visited 用来存储已经访问过的顶点。
5，使用最小优先级队列来存储边，
接下来 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)
1，将图中所有的顶点拷贝到最小生成树的图中。
2，从图中选择一个起始顶点。
3，将起始顶点标记为已访问过。
4，将所有已访问过顶点的边，加入到最低优先级队列中。
最后，完善 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
1，如果队列不为空，继续该算法。
2，获得最小边的目的顶点。
3，如果该顶点已经访问过，则继续该循环。
4，将顶点标记为已经访问过。
5，将边的权重加到总的 cost 里面。
6，将最小边加到最小生成树的图中。
7，将当前顶点所有的边加到优先级队列中。
8，一旦 priorityQueue为空，则返回总的最小权重和最小生成树。
最后附上本文的相关代码DataAndAlgorim
网友评论