Swift 算法实战之路：深度和广度优先搜索

567 查看

之前谈到了最简单的搜索法：二分搜索。虽然它的算法复杂度非常低只有O(logn)，但使用起来也有局限：只有在输入是排序的情况下才能使用。这次讲解两个更复杂的搜索算法 — 深度优先搜索（Depth-First-Search，以下简称DFS）和广度优先搜索（Breadth-First-Search，以下简称BFS）。

基本概念

DFS和BFS的具体定义这里不做赘述。笔者谈谈自己对此的形象理解：假如你在家中发现钥匙不见了，为了找到钥匙，你有两种选择：

从当前角落开始，顺着一个方向不停的找。假如这个方向全部搜索完毕依然没有找到钥匙，就回到起始角落，从另一个方向寻找，直到找到钥匙或所有方向都搜索完毕为止。这种方法就是DFS。
从当前角落开始，每次把最近所有方向的角落全部搜索一遍，直到找到钥匙或所有方向都搜索完毕为止。这种方法就是BFS。

我们假设共有10个角落，起始角落为1，它的周围有4个方向，如下图：

DFS的搜索步骤为

1
2 -> 3 -> 4
5
6 ->7 -> 8
9 -> 10

即每次把一个方向彻底搜索完全后，才返回搜索下一个方向。
BFS的搜索步骤为

1
2 -> 5 -> 6 -> 9
3 -> 4
7
10
8

即每次访问上一步周围所有方向上的角落。
细心的朋友会记得，我之前在讲二叉树的时候，讲到了前序遍历和层级遍历，而这两者本质上就是DFS和BFS。

DFS的Swift实现：

func dfs(root: Node?) {

guard let root = root else {

return

}

visit(root)

root.visited = true

for node in root.neighbors {

if !node.visited {

dfs(node)

}

BFS的Swift实现：

func bfs(root: Node?) {

var queue = [Node]()

if let root = root {

queue.append(root)

}

while !queue.isEmpty {

let current = queue.removeFirst()

visit(current)

current.visited = true

for node in current.neighbors {

if !node.visited {

queue.append(node)

}

永远记住：DFS的实现用递归，BFS的实现用循环（配合队列）。

iOS实战演练

硅谷面试iOS工程师，有这样一个环节，给你1 ~ 1.5小时，从头开始实现一个小App。我们来看这样一个题目：

实现一个找单词App: 给定一个初始的字母矩阵，你可以从任一字母开始，上下左右，任意方向、任意长度，选出其中所有单词。

找单词App

很多人拿到这道题目就懵了。。。完全不是我们熟悉的UITableView或者UICollectionView啊，这要咋整。我们来一步步分析。

第一步：实现字母矩阵

首先，我们肯定有个字符二阶矩阵作为输入，姑且记做：matrix: [[Character]]。现在要把它展现在手机上，那么可行的方法，就是创建一个UILabel二维矩阵，记做labels: [[UILabel]]，矩阵中每一个UILabel对应的内容就是相应的字母。同时，我们可以维护2个全局变量，xOffset和yOffset。然后在for循环中创建相应的UILabel同时将其添加进lables中便于以后使用，代码如下：

var xOffset = 0

var yOffset = 0

let cellWidth = UIScreen.mainScreen().bounds.size.width / matrix[0].count

let cellHeight = UIScreen.mainScreen().bounds.size.height / matrix.count

for i in 0 ..< matrix.count {

for j in 0 ..< matrix[0].count {

let label = UILabel(frame: CGRect(x: xOffset, y: yOffset, width: cellWidth, height: cellHeight))

label.text = String(matrix[i][j])

view.addSubView(label)

labels.append(label)

xOffset += cellWidth

}

xOffset = 0

yOffset += cellHeight

}

第二步：用DFS实现搜索单词

现在要实现搜索单词的核心算法了。我们先简化要求，假如只在字母矩阵中搜索单词”crowd”该怎么做？
首先我们要找到 “c” 这个字母所在的位置，然后再上下左右找第二个字母 “r” ，接着再找字母 “o” 。。。以此类推，直到找到最后一个字母 “d” 。如果没有找到相应的字母，我们就回头去首字母 “c” 所在的另一个位置，重新搜索。
这里要注意一个细节，就是我们不能回头搜索字母。比如我们已经从 “c” 开始向上走搜索到了 “r” ，这个时候就不能从 “r” 向下回头 — 因为 “c” 已经访问过了。所以这里需要一个var visited: [[Bool]] 来记录访问记录。代码如下：

基本概念

DFS和BFS的具体定义这里不做赘述。笔者谈谈自己对此的形象理解：假如你在家中发现钥匙不见了，为了找到钥匙，你有两种选择：

从当前角落开始，顺着一个方向不停的找。假如这个方向全部搜索完毕依然没有找到钥匙，就回到起始角落，从另一个方向寻找，直到找到钥匙或所有方向都搜索完毕为止。这种方法就是DFS。
从当前角落开始，每次把最近所有方向的角落全部搜索一遍，直到找到钥匙或所有方向都搜索完毕为止。这种方法就是BFS。

我们假设共有10个角落，起始角落为1，它的周围有4个方向，如下图：

DFS的搜索步骤为

1
2 -> 3 -> 4
5
6 ->7 -> 8
9 -> 10

即每次把一个方向彻底搜索完全后，才返回搜索下一个方向。
BFS的搜索步骤为

1
2 -> 5 -> 6 -> 9
3 -> 4
7
10
8

DFS的Swift实现：

func dfs(root: Node?) {

guard let root = root else {

return

}

visit(root)

root.visited = true

for node in root.neighbors {

if !node.visited {

dfs(node)

}

BFS的Swift实现：

func bfs(root: Node?) {

var queue = [Node]()

if let root = root {

queue.append(root)

}

while !queue.isEmpty {

let current = queue.removeFirst()

visit(current)

current.visited = true

for node in current.neighbors {

if !node.visited {

queue.append(node)

}

永远记住：DFS的实现用递归，BFS的实现用循环（配合队列）。

iOS实战演练

硅谷面试iOS工程师，有这样一个环节，给你1 ~ 1.5小时，从头开始实现一个小App。我们来看这样一个题目：

实现一个找单词App: 给定一个初始的字母矩阵，你可以从任一字母开始，上下左右，任意方向、任意长度，选出其中所有单词。

找单词App

很多人拿到这道题目就懵了。。。完全不是我们熟悉的UITableView或者UICollectionView啊，这要咋整。我们来一步步分析。

第一步：实现字母矩阵

var xOffset = 0

var yOffset = 0

let cellWidth = UIScreen.mainScreen().bounds.size.width / matrix[0].count

let cellHeight = UIScreen.mainScreen().bounds.size.height / matrix.count

for i in 0 ..< matrix.count {

for j in 0 ..< matrix[0].count {

let label = UILabel(frame: CGRect(x: xOffset, y: yOffset, width: cellWidth, height: cellHeight))

label.text = String(matrix[i][j])

view.addSubView(label)

labels.append(label)

xOffset += cellWidth

}

xOffset = 0

yOffset += cellHeight

}