【译】Swift算法俱乐部-最小生成树（加权图）

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙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中是安全的。

下图演示了这个步骤：

Graph

准备

// 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中。

下图演示了这个步骤：

Graph

准备

// 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