Fork me on GitHub

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

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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

准备

1
2
3
4
5
6
7
8
9
10
// 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)
}

排序边:

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

一次取一个边并尝试将其插入MST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

准备

1
2
3
4
5
6
7
8
// 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 })

排序顶点:

1
priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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

坚持原创技术分享,您的支持将鼓励我继续创作!