本文是對(duì) Swift Algorithm Club 翻譯的一篇文章啄寡。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項(xiàng)目，目前在GitHub上有18000+??另患，我初略統(tǒng)計(jì)了一下，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)降铸，基本上常見的都包含了住拭，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源。
??andyRon/swift-algorithm-club-cn是我對(duì)Swift Algorithm Club柱嫌，邊學(xué)習(xí)邊翻譯的項(xiàng)目锋恬。由于能力有限，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥编丘，請(qǐng)指正与学，歡迎pull request。也歡迎有興趣嘉抓、有時(shí)間的小伙伴一起參與翻譯和學(xué)習(xí)??索守。當(dāng)然也歡迎加??，??????????抑片。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Depth-First Search
深度優(yōu)先搜索(DFS卵佛，Depth-First Search)
這個(gè)主題已經(jīng)有輔導(dǎo)文章
深度優(yōu)先搜索（DFS）是用于遍歷或搜索樹或圖數(shù)據(jù)結(jié)構(gòu)的算法。它從源節(jié)點(diǎn)開始，并在回溯之前盡可能地沿著每個(gè)分支進(jìn)行探索截汪。
深度優(yōu)先搜索可以用于有向圖和無向圖疾牲。
動(dòng)畫示例
以下是深度優(yōu)先搜索在圖上的工作方式：
假設(shè)我們從節(jié)點(diǎn)A開始搜索。 在深度優(yōu)先搜索中衙解，我們查看起始節(jié)點(diǎn)的第一個(gè)鄰居并訪問它阳柔，在這個(gè)示例中是節(jié)點(diǎn)B。然后我們查找節(jié)點(diǎn)B的第一個(gè)鄰居并訪問它蚓峦，它是節(jié)點(diǎn)D舌剂。由于D沒有自己的任何未訪問的鄰居節(jié)點(diǎn)，我們回溯到節(jié)點(diǎn)B并轉(zhuǎn)到其另外的鄰居節(jié)點(diǎn)E暑椰。依此類推霍转，直到我們?cè)L問了圖中的所有節(jié)點(diǎn)。
每當(dāng)我們?cè)L問第一個(gè)鄰居節(jié)點(diǎn)并繼續(xù)前進(jìn)干茉，直到無處可去谴忧，然后我們回溯到之前訪問的節(jié)點(diǎn)。 當(dāng)我們一直回溯到節(jié)點(diǎn)A時(shí)角虫，搜索就完成了沾谓。
對(duì)于上面的例子，是按照A戳鹅，B均驶，D，E枫虏，H妇穴，F，G隶债，C的順序訪問節(jié)點(diǎn)的腾它。
深度優(yōu)先搜索過程也可以顯示為樹：
節(jié)點(diǎn)的父節(jié)點(diǎn)是“發(fā)現(xiàn)”該節(jié)點(diǎn)的節(jié)點(diǎn)。 樹的根是您開始深度優(yōu)先搜索的節(jié)點(diǎn)死讹。 每當(dāng)有一個(gè)分支時(shí)瞒滴，那就是我們回溯的地方。
代碼
深度優(yōu)先搜索的簡單遞歸實(shí)現(xiàn)：
func depthFirstSearch(_ graph: Graph, source: Node) -> [String] {
var nodesExplored = [source.label]
source.visited = true
for edge in source.neighbors {
if !edge.neighbor.visited {
nodesExplored += depthFirstSearch(graph, source: edge.neighbor)
}
}
return nodesExplored
}
廣度優(yōu)先搜索首先訪問所有直接鄰居赞警，而深度優(yōu)先搜索嘗試盡可能地深入樹或圖妓忍。
在 playground 里測(cè)試：
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")
graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeD)
graph.addEdge(nodeB, neighbor: nodeE)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeG)
graph.addEdge(nodeE, neighbor: nodeH)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeG)
let nodesExplored = depthFirstSearch(graph, source: nodeA)
print(nodesExplored)
打印結(jié)果是： ["a", "b", "d", "e", "h", "f", "g", "c"]
DFS有什么用？
深度優(yōu)先搜索可用于解決許多問題愧旦，例如：
- 查找稀疏圖的連通分量
- 圖中節(jié)點(diǎn)的拓?fù)渑判?/a>
- 查找圖的橋梁（參見：Bridges）
- 還有很多其它應(yīng)用世剖！
作者：Paulo Tanaka，Matthijs Hollemans
翻譯：Andy Ron
校對(duì)：Andy Ron
