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

Swift Algorithm Clubraywenderlich.com 网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+:star:️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

:octopus: andyRon/swift-algorithm-club-cn 是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习 。当然也欢迎加:star:️， 。

### 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.

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.
}


let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight <$1.weight })


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

// Put the two vertices into the same set.
unionFind.unionSetsContaining(v1, and: v2)
}
}


### Prim算法

Prim算法不会对所有边进行预排序。相反，它使用 优先队列 来维护正在运行的已排序的下一个可能的顶点。

// 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() {
if visited.contains(vertex) {
continue
}

// If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.
visited.insert(vertex)
if let prev = head.parent { // The first vertex doesn't have a parent.
}

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