【译】Swift算法俱乐部-最小生成树（加权图）
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club 是 raywenderlich.com 网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+:star:️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
:octopus: andyRon/swift-algorithm-club-cn 是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习 。当然也欢迎加:star:️， 。
本文的翻译原文和代码可以查看:octopus: swift-algorithm-club-cn/Minimum Spanning Tree
最小生成树（加权图）（Minimum Spanning Tree (Weighted Graph)）
这个主题有一篇辅导 文章
连接的无向加权图的 最小生成树 （MST）具有来自原始图的边的子集，其将所有顶点连接在一起，没有任何循环并尽可能减少总边权重。 图中可以有多个MST。
有两种流行的算法来计算图形的MST – Kruskal算法 和 Prim算法 。 两种算法的总时间复杂度为 O(ElogE) ，其中 E 是原始图的边数。
Kruskal算法
Sort the edges base on weight. Greedily select the smallest one each time and add into the MST as long as it doesn’t form a cycle.
根据权重对边进行排序。每次贪婪地选择最小的一个并且只要它不形成循环就加入MST。
Kruskal的算法使用 并查集 数据结构来检查是否有任何其他边导致循环。逻辑是将所有连接的顶点放在同一个集合中（在并查集的概念中）。如果来自新边的两个顶点不属于同一个集合，那么将该边添加到MST中是安全的。
下图演示了这个步骤：
准备
// Initialize the values to be returned and Union Find data structure.
var cost: Int = 0
var tree = Graph()
var unionFind = UnionFind()
for vertex in graph.vertices {
// Initially all vertices are disconnected.
// Each of them belongs to it's individual set.
unionFind.addSetWith(vertex)
}
排序边：
let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight })
一次取一个边并尝试将其插入MST。
for edge in sortedEdgeListByWeight {
let v1 = edge.vertex1
let v2 = edge.vertex2
// Same set means the two vertices of this edge were already connected in the MST.
// Adding this one will cause a cycle.
if !unionFind.inSameSet(v1, and: v2) {
// Add the edge into the MST and update the final cost.
cost += edge.weight
tree.addEdge(edge)
// Put the two vertices into the same set.
unionFind.unionSetsContaining(v1, and: v2)
}
}
Prim算法
Prim算法不会对所有边进行预排序。相反，它使用 优先队列 来维护正在运行的已排序的下一个可能的顶点。
从一个顶点开始，循环遍历所有未访问的邻居，并为每个邻居入队一对值 —— 顶点和将当前顶点连接到邻居的边的权重。每次贪婪地选择优先队列的顶部（权重值最小的那个）顶点，如果尚未访问已入队的邻居，则将边添加到最终的MST中。
下图演示了这个步骤：
准备
// Initialize the values to be returned and Priority Queue data structure.
var cost: Int = 0
var tree = Graph()
var visited = Set()
// In addition to the (neighbour vertex, weight) pair, parent is added for the purpose of printing out the MST later.
// parent is basically current vertex. aka. the previous vertex before neigbour vertex gets visited.
var priorityQueue = PriorityQueue(sort: { $0.weight < $1.weight })
排序顶点：
priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))
// Take from the top of the priority queue ensures getting the least weight edge.
while let head = priorityQueue.dequeue() {
let vertex = head.vertex
if visited.contains(vertex) {
continue
}
// If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.
visited.insert(vertex)
cost += head.weight
if let prev = head.parent { // The first vertex doesn't have a parent.
tree.addEdge(vertex1: prev, vertex2: vertex, weight: head.weight)
}
// Add all unvisted neighbours into the priority queue.
if let neighbours = graph.adjList[vertex] {
for neighbour in neighbours {
let nextVertex = neighbour.vertex
if !visited.contains(nextVertex) {
priorityQueue.enqueue((vertex: nextVertex, weight: neighbour.weight, parent: vertex))
}
}
}
}
翻译： Andy Ron
校对： Andy Ron
About The Author
