本文是對 Swift Algorithm Club 翻譯的一篇文章助被。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項目剖张，目前在GitHub上有18000+??切诀，我初略統(tǒng)計了一下，大概有一百左右個的算法和數(shù)據(jù)結(jié)構(gòu)搔弄，基本上常見的都包含了幅虑，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯的資源。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club顾犹，邊學(xué)習(xí)邊翻譯的項目。由于能力有限，如發(fā)現(xiàn)錯誤或翻譯不妥，請指正极阅，歡迎pull request。也歡迎有興趣、有時間的小伙伴一起參與翻譯和學(xué)習(xí)??帖族。當(dāng)然也歡迎加??茶鹃，??????????。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Minimum Spanning Tree(Unweighted)
最小生成樹（未加權(quán)圖）（Minimum Spanning Tree (Unweighted Graph)）
最小生成樹描述了包含訪問圖中每個節(jié)點所需的最小數(shù)目邊的路徑。
看下圖：
如果我們從節(jié)點a開始并想要訪問每個其他節(jié)點逞怨，那么最有效的路徑是什么革砸？ 我們可以使用最小生成樹算法來計算它。
這是圖的最小生成樹。 它由粗體邊表示：
繪制為更一般形式的樹扒怖，它看起來像這樣：
要計算未加權(quán)圖上的最小生成樹蚂蕴，我們可以使用廣度優(yōu)先搜索 算法鸟整。廣度優(yōu)先搜索從源節(jié)點開始，并在移動到下一級鄰居之前首先通過探索直接鄰居節(jié)點來遍歷圖涉茧。如果我們通過選擇性地刪除邊來調(diào)整此算法钳垮，那么它可以將圖轉(zhuǎn)換為最小生成樹。
讓我們逐步完成這個例子。 我們從源節(jié)點a開始，將其添加到隊列中并將其標(biāo)記為已訪問。
queue.enqueue(a)
a.visited = true
隊列現(xiàn)在是[a]。 與廣度優(yōu)先搜索一樣落追，我們將隊列前面的節(jié)點a出隊病苗，并將其直接鄰居節(jié)點b和h入隊。 將它們標(biāo)記為訪問過挚赊。
queue.dequeue() // a
queue.enqueue(b)
b.visited = true
queue.enqueue(h)
h.visited = true
隊列現(xiàn)在是[b, h]。 將b出隊并將鄰居節(jié)點c入隊箕宙。 將其標(biāo)記為已訪問柬帕。 將b到h邊移除凤跑，因為已經(jīng)訪問過h。
queue.dequeue() // b
queue.enqueue(c)
c.visited = true
b.removeEdgeTo(h)
隊列現(xiàn)在是[h, c]。 將h出隊并將鄰居節(jié)點g和i入隊耍群，并將它們標(biāo)記為已訪問曹抬。
queue.dequeue() // h
queue.enqueue(g)
g.visited = true
queue.enqueue(i)
i.visited = true
隊列現(xiàn)在是[c, g, i]。 將c出隊并將鄰居節(jié)點d和f入隊，并將它們標(biāo)記為已訪問。 刪除c和i之間的邊壳咕，因為已經(jīng)訪問了i。
queue.dequeue() // c
queue.enqueue(d)
d.visited = true
queue.enqueue(f)
f.visited = true
c.removeEdgeTo(i)
隊列現(xiàn)在是[g, i, d, f]。 出隊g地啰。 它的所有鄰居都已經(jīng)被發(fā)現(xiàn)了亏吝，所以沒有什么可以入隊的止喷。 刪除g到f的邊预愤，以及g到i的邊嗜傅，因為已經(jīng)發(fā)現(xiàn)了f和i。
queue.dequeue() // g
g.removeEdgeTo(f)
g.removeEdgeTo(i)
隊列現(xiàn)在是[i, d, f]乒融。 出隊i掰盘。 這個節(jié)點沒有別的辦法。
queue.dequeue() // i
隊列現(xiàn)在是[d, f]赞季。 將d出隊并將鄰居節(jié)點e入隊愧捕。 將其標(biāo)記為已訪問。 刪除d到f的邊申钩，因為已經(jīng)訪問了f次绘。
queue.dequeue() // d
queue.enqueue(e)
e.visited = true
d.removeEdgeTo(f)
隊列現(xiàn)在是[f, e]。 出列f撒遣。 刪除f和e之間的邊邮偎，因為已經(jīng)訪問過e。
queue.dequeue() // f
f.removeEdgeTo(e)
隊列現(xiàn)在是[e]义黎。 出隊e钢猛。
queue.dequeue() // e
隊列為空，這意味著已計算出最小生成樹轩缤。
代碼如下：
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
}
此函數(shù)返回一個新的Graph對象，該對象僅描述最小生成樹贩绕。 在圖中火的，這將是僅包含粗體邊的圖。
將此代碼放在playground上淑倾，進行測試：
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"]]
注意： 在未加權(quán)的圖上馏鹤，任何生成樹始終是最小生成樹。 這意味著您還可以使用深度優(yōu)先搜索來查找最小生成樹娇哆。
作者：Chris Pilcher湃累， Matthijs Hollemans
翻譯：Andy Ron
校對：Andy Ron
