【译】Swift算法俱乐部-深度优先搜索
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Depth-First Search
深度优先搜索(DFS，Depth-First Search)
这个主题已经有辅导文章
深度优先搜索（DFS）是用于遍历或搜索树或图数据结构的算法。它从源节点开始，并在回溯之前尽可能地沿着每个分支进行探索。
深度优先搜索可以用于有向图和无向图。
动画示例
以下是深度优先搜索在图上的工作方式：
Animated example
假设我们从节点A开始搜索。 在深度优先搜索中，我们查看起始节点的第一个邻居并访问它，在这个示例中是节点B。然后我们查找节点B的第一个邻居并访问它，它是节点D。由于D没有自己的任何未访问的邻居节点，我们回溯到节点B并转到其另外的邻居节点E。依此类推，直到我们访问了图中的所有节点。
每当我们访问第一个邻居节点并继续前进，直到无处可去，然后我们回溯到之前访问的节点。 当我们一直回溯到节点A时，搜索就完成了。
对于上面的例子，是按照A，B，D，E，H，F，G，C的顺序访问节点的。
深度优先搜索过程也可以显示为树：
Traversal tree
节点的父节点是“发现”该节点的节点。 树的根是您开始深度优先搜索的节点。 每当有一个分支时，那就是我们回溯的地方。
代码
深度优先搜索的简单递归实现：
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
}
广度优先搜索首先访问所有直接邻居，而深度优先搜索尝试尽可能地深入树或图。
在 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")
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)
打印结果是： ["a", "b", "d", "e", "h", "f", "g", "c"]
DFS有什么用？
深度优先搜索可用于解决许多问题，例如：
