【译】Swift算法俱乐部-最小生成树（加权图）
source link: https://www.tuicool.com/articles/Vfmyyyj
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文是对 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<T>()
var unionFind = UnionFind<T>()
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<T>()
var visited = Set<T>()
// 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<(vertex: T, weight: Int, parent: T?)>(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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK