【译】数据结构与算法——深度优先搜索

发表于 分类于

深度优先搜索(DFS)是遍历或搜索树 或 图等数据结构的一种算法。从源点开始，在回溯之前尽量遍历较远的每一个分支。

深度优先搜索既适用于有向图也适用于无向图。

动画示例

下面演示了深度优先搜索是如何搜索一张图的：

Animated example

首先从 A 节点开始。我们先寻找该节点的第一个临近节点，并访问它，即示例中的节点 B。之后，在查找 B 节点的第一个临近节点，并访问它即节点 D。至此，D 节点已经没有未被访问过的临近节点，此时回溯到节点 B并访问它的另一个临近节点 E。依此类推，直至访问完图中所有节点。

依次访问它的第一个临近节点，直至无法继续，然后在回溯到可继续的那个节点（即存在未被访问的临近节点）。到回溯完所有路径并返回起始节点 A 时，搜索完毕。

以上图为例，依次访问的节点顺序为：A, B, D, E, H, F, G, C。
For the example, the nodes were visited in the order A, B, D, E, H, F, G, C.

深度优先搜索的过程也可以以树的形式呈现：

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适用哪些场景呢？

深度优先搜索可以用来解决很多问题，例如：

该系列文章翻译自 Raywenderlich 的开源项目：swift-algorithm-club，意在帮助有一定基础的同学进行回顾，如果你才接触，那么建议移步详细教程

Written for Swift Algorithm Club by Paulo Tanaka and Matthijs Hollemans

由 William Han 翻译