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/Depth-First Search


深度优先搜索(DFS,Depth-First Search)

这个主题已经有辅导文章

深度优先搜索(DFS)是用于遍历或搜索数据结构的算法。它从源节点开始,并在回溯之前尽可能地沿着每个分支进行探索。

深度优先搜索可以用于有向图和无向图。

动画示例

以下是深度优先搜索在图上的工作方式:

Animated example

假设我们从节点A开始搜索。 在深度优先搜索中,我们查看起始节点的第一个邻居并访问它,在这个示例中是节点B。然后我们查找节点B的第一个邻居并访问它,它是节点D。由于D没有自己的任何未访问的邻居节点,我们回溯到节点B并转到其另外的邻居节点E。依此类推,直到我们访问了图中的所有节点。

每当我们访问第一个邻居节点并继续前进,直到无处可去,然后我们回溯到之前访问的节点。 当我们一直回溯到节点A时,搜索就完成了。

对于上面的例子,是按照ABDEHFGC的顺序访问节点的。

深度优先搜索过程也可以显示为树:

Traversal tree

节点的父节点是“发现”该节点的节点。 树的根是您开始深度优先搜索的节点。 每当有一个分支时,那就是我们回溯的地方。

代码

深度优先搜索的简单递归实现:

1
2
3
4
5
6
7
8
9
10
11
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 里测试:

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

深度优先搜索可用于解决许多问题,例如:

  • 查找稀疏图的连通分量
  • 图中节点的拓扑排序
  • 查找图的桥梁(参见:Bridges#Bridge-finding_algorithm))
  • 还有很多其它应用!

作者:Paulo Tanaka,Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

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