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(Unweighted))


最小生成树(未加权图)(Minimum Spanning Tree (Unweighted Graph))

最小生成树描述了包含访问图中每个节点所需的最小数目边的路径。

看下图:

Graph

如果我们从节点a开始并想要访问每个其他节点,那么最有效的路径是什么? 我们可以使用最小生成树算法来计算它。

这是图的最小生成树。 它由粗体边表示:

Minimum spanning tree

绘制为更一般形式的树,它看起来像这样:

An actual tree

要计算未加权图上的最小生成树,我们可以使用广度优先搜索 算法。广度优先搜索从源节点开始,并在移动到下一级邻居之前首先通过探索直接邻居节点来遍历图。如果我们通过选择性地删除边来调整此算法,那么它可以将图转换为最小生成树。

让我们逐步完成这个例子。 我们从源节点a开始,将其添加到队列中并将其标记为已访问。

1
2
queue.enqueue(a)
a.visited = true

队列现在是[a]。 与广度优先搜索一样,我们将队列前面的节点a出队,并将其直接邻居节点bh入队。 将它们标记为访问过。

1
2
3
4
5
queue.dequeue()   // a
queue.enqueue(b)
b.visited = true
queue.enqueue(h)
h.visited = true

队列现在是[b, h]。 将b出队并将邻居节点c入队。 将其标记为已访问。 将bh边移除,因为已经访问过h

1
2
3
4
queue.dequeue()   // b
queue.enqueue(c)
c.visited = true
b.removeEdgeTo(h)

队列现在是[h, c]。 将h出队并将邻居节点gi入队,并将它们标记为已访问。

1
2
3
4
5
queue.dequeue()   // h
queue.enqueue(g)
g.visited = true
queue.enqueue(i)
i.visited = true

队列现在是[c, g, i]。 将c出队并将邻居节点df入队,并将它们标记为已访问。 删除ci之间的边,因为已经访问了i

1
2
3
4
5
6
queue.dequeue()   // c
queue.enqueue(d)
d.visited = true
queue.enqueue(f)
f.visited = true
c.removeEdgeTo(i)

队列现在是[g, i, d, f]。 出队g。 它的所有邻居都已经被发现了,所以没有什么可以入队的。 删除gf的边,以及gi的边,因为已经发现了fi

1
2
3
queue.dequeue()   // g
g.removeEdgeTo(f)
g.removeEdgeTo(i)

队列现在是[i, d, f]。 出队i。 这个节点没有别的办法。

1
queue.dequeue()   // i

队列现在是[d, f]。 将d出队并将邻居节点e入队。 将其标记为已访问。 删除df的边,因为已经访问了f

1
2
3
4
queue.dequeue()   // d
queue.enqueue(e)
e.visited = true
d.removeEdgeTo(f)

队列现在是[f, e]。 出列f。 删除fe之间的边,因为已经访问过e

1
2
queue.dequeue()   // f
f.removeEdgeTo(e)

队列现在是[e]。 出队e

1
queue.dequeue()   // e

队列为空,这意味着已计算出最小生成树。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func breadthFirstSearchMinimumSpanningTree(graph: Graph, source: Node) -> Graph {
let minimumSpanningTree = graph.duplicate()

var queue = Queue<Node>()
let sourceInMinimumSpanningTree = minimumSpanningTree.findNodeWithLabel(source.label)
queue.enqueue(sourceInMinimumSpanningTree)
sourceInMinimumSpanningTree.visited = true

while let current = queue.dequeue() {
for edge in current.neighbors {
let neighborNode = edge.neighbor
if !neighborNode.visited {
neighborNode.visited = true
queue.enqueue(neighborNode)
} else {
current.remove(edge)
}
}
}

return minimumSpanningTree
}

此函数返回一个新的Graph对象,该对象仅描述最小生成树。 在图中,这将是仅包含粗体边的图。

将此代码放在playground上,进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")
let nodeI = graph.addNode("i")

graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeH)
graph.addEdge(nodeB, neighbor: nodeA)
graph.addEdge(nodeB, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeH)
graph.addEdge(nodeC, neighbor: nodeB)
graph.addEdge(nodeC, neighbor: nodeD)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeI)
graph.addEdge(nodeD, neighbor: nodeC)
graph.addEdge(nodeD, neighbor: nodeE)
graph.addEdge(nodeD, neighbor: nodeF)
graph.addEdge(nodeE, neighbor: nodeD)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeC)
graph.addEdge(nodeF, neighbor: nodeD)
graph.addEdge(nodeF, neighbor: nodeE)
graph.addEdge(nodeF, neighbor: nodeG)
graph.addEdge(nodeG, neighbor: nodeF)
graph.addEdge(nodeG, neighbor: nodeH)
graph.addEdge(nodeG, neighbor: nodeI)
graph.addEdge(nodeH, neighbor: nodeA)
graph.addEdge(nodeH, neighbor: nodeB)
graph.addEdge(nodeH, neighbor: nodeG)
graph.addEdge(nodeH, neighbor: nodeI)
graph.addEdge(nodeI, neighbor: nodeC)
graph.addEdge(nodeI, neighbor: nodeG)
graph.addEdge(nodeI, neighbor: nodeH)

let minimumSpanningTree = breadthFirstSearchMinimumSpanningTree(graph, source: nodeA)

print(minimumSpanningTree) // [node: a edges: ["b", "h"]]
// [node: b edges: ["c"]]
// [node: c edges: ["d", "f"]]
// [node: d edges: ["e"]]
// [node: h edges: ["g", "i"]]

注意: 在未加权的图上,任何生成树始终是最小生成树。 这意味着您还可以使用深度优先搜索来查找最小生成树。

作者:Chris Pilcher, Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

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