之前談到了最簡(jiǎn)單的搜索法：二分搜索。雖然它的算法復(fù)雜度非常低只有O(logn)，但使用起來(lái)也有局限：只有在輸入是排序的情況下才能使用。這次講解兩個(gè)更復(fù)雜的搜索算法 -- 深度優(yōu)先搜索（Depth-First-Search，以下簡(jiǎn)稱(chēng)DFS）和廣度優(yōu)先搜索（Breadth-First-Search，以下簡(jiǎn)稱(chēng)BFS）。
基本概念
DFS和BFS的具體定義這里不做贅述。筆者談?wù)勛约簩?duì)此的形象理解：假如你在家中發(fā)現(xiàn)鑰匙不見(jiàn)了，為了找到鑰匙，你有兩種選擇：
- 從當(dāng)前角落開(kāi)始，順著一個(gè)方向不停的找。假如這個(gè)方向全部搜索完畢依然沒(méi)有找到鑰匙，就回到起始角落，從另一個(gè)方向?qū)ふ?，直到找到鑰匙或所有方向都搜索完畢為止。這種方法就是DFS。
- 從當(dāng)前角落開(kāi)始，每次把最近所有方向的角落全部搜索一遍，直到找到鑰匙或所有方向都搜索完畢為止。這種方法就是BFS。
我們假設(shè)共有10個(gè)角落，起始角落為1，它的周?chē)?個(gè)方向，如下圖：
DFS的搜索步驟為
- 1
- 2 -> 3 -> 4
- 5
- 6 ->7 -> 8
- 9 -> 10
即每次把一個(gè)方向徹底搜索完全后，才返回搜索下一個(gè)方向。
BFS的搜索步驟為
- 1
- 2 -> 5 -> 6 -> 9
- 3 -> 4
- 7
- 10
- 8
即每次訪(fǎng)問(wèn)上一步周?chē)蟹较蛏系慕锹?/strong>。
細(xì)心的朋友會(huì)記得，我之前在講二叉樹(shù)的時(shí)候，講到了前序遍歷和層級(jí)遍歷，而這兩者本質(zhì)上就是DFS和BFS。
DFS的Swift實(shí)現(xiàn)：
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實(shí)現(xiàn)：
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)
}
}
}
}
永遠(yuǎn)記?。?strong>DFS的實(shí)現(xiàn)用遞歸，BFS的實(shí)現(xiàn)用循環(huán)（配合隊(duì)列）。
iOS實(shí)戰(zhàn)演練
硅谷面試iOS工程師，有這樣一個(gè)環(huán)節(jié)，給你1 ~ 1.5小時(shí)，從頭開(kāi)始實(shí)現(xiàn)一個(gè)小App。我們來(lái)看這樣一個(gè)題目：
實(shí)現(xiàn)一個(gè)找單詞App: 給定一個(gè)初始的字母矩陣，你可以從任一字母開(kāi)始，上下左右，任意方向、任意長(zhǎng)度，選出其中所有單詞。
很多人拿到這道題目就懵了。。。完全不是我們熟悉的UITableView或者UICollectionView啊，這要咋整。我們來(lái)一步步分析。
第一步：實(shí)現(xiàn)字母矩陣
首先，我們肯定有個(gè)字符二階矩陣作為輸入，姑且記做：matrix: [[Character]]?，F(xiàn)在要把它展現(xiàn)在手機(jī)上，那么可行的方法，就是創(chuàng)建一個(gè)UILabel二維矩陣，記做labels: [[UILabel]]，矩陣中每一個(gè)UILabel對(duì)應(yīng)的內(nèi)容就是相應(yīng)的字母。同時(shí)，我們可以維護(hù)2個(gè)全局變量，xOffset和yOffset。然后在for循環(huán)中創(chuàng)建相應(yīng)的UILabel同時(shí)將其添加進(jìn)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實(shí)現(xiàn)搜索單詞
現(xiàn)在要實(shí)現(xiàn)搜索單詞的核心算法了。我們先簡(jiǎn)化要求，假如只在字母矩陣中搜索單詞"crowd"該怎么做？
首先我們要找到 "c" 這個(gè)字母所在的位置，然后再上下左右找第二個(gè)字母 "r" ，接著再找字母 "o" 。。。以此類(lèi)推，直到找到最后一個(gè)字母 "d" 。如果沒(méi)有找到相應(yīng)的字母，我們就回頭去首字母 "c" 所在的另一個(gè)位置，重新搜索。
這里要注意一個(gè)細(xì)節(jié)，就是我們不能回頭搜索字母。比如我們已經(jīng)從 "c" 開(kāi)始向上走搜索到了 "r" ，這個(gè)時(shí)候就不能從 "r" 向下回頭 -- 因?yàn)?"c" 已經(jīng)訪(fǎng)問(wèn)過(guò)了。所以這里需要一個(gè)var visited: [[Bool]] 來(lái)記錄訪(fǎng)問(wèn)記錄。代碼如下：
func searchWord(_ board: [[Character]]) -> Bool {
guard board.count > 0 && board[0].count > 0 else {
return false
}
let (m, n) = (board.count, board[0].count)
var visited = Array(repeating: Array(repeating: false, count: n), count: m)
var wordContent = [Character]("crowd".characters)
for i in 0 ..< m {
for j in 0 ..< n {
if dfs(board, wordContent, m, n, i, j, &visited, 0) {
return true
}
}
}
return false
}
func dfs(_ board: [[Character]], _ wordContent: [Character], _ m: Int, _ n: Int, _ i: Int, _ j: Int, _ visited: inout [[Bool]], _ index: Int) -> Bool {
if index == wordContent.count {
return true
}
guard i >= 0 && i < m && j >= 0 && j < n else {
return false
}
guard !visited[i][j] && board[i][j] == wordContent[index] else {
return false
}
visited[i][j] = true
if dfs(board, wordContent, m, n, i + 1, j, &visited, index + 1) || dfs(board, wordContent, m, n, i - 1, j, &visited, index + 1) || dfs(board, wordContent, m, n, i, j + 1, &visited, index + 1) || dfs(board, wordContent, m, n, i, j - 1, &visited, index + 1) {
return true
}
visited[i][j] = false
return false
}
第三步：優(yōu)化算法，進(jìn)階
好了現(xiàn)在我們已經(jīng)知道了怎么搜索一個(gè)單詞了，那么多個(gè)單詞怎么搜索？首先題目是要求找出所有的單詞，那么肯定事先有個(gè)字典，根據(jù)這個(gè)字典，我們可以知道所選字母是不是可以構(gòu)成一個(gè)單詞。所以題目就變成了：
已知一個(gè)字母構(gòu)成的二維矩陣，并給定一個(gè)字典。選出二維矩陣中所有橫向或者縱向的單詞。
也就是實(shí)現(xiàn)以下函數(shù)：
func findWords(_ board: [[Character]], _ dict: Set<String>) -> [String] {}
我們剛才已經(jīng)知道如何在矩陣中搜索一個(gè)單詞了。所以最暴力的做法，就是在矩陣中，搜索所有字典中的單詞，如果存在就添加在輸出中。
這個(gè)做法顯然復(fù)雜度極高：首先，每次DFS的復(fù)雜度就是O(n2)，字母矩陣越大，搜索時(shí)間就越長(zhǎng)；其次，字典可能會(huì)非常大，如果每個(gè)單詞都搜索一遍，開(kāi)銷(xiāo)太大。這種做法的總復(fù)雜度為O(m·n2)，其中m為字典中單詞的數(shù)量，n為矩陣的邊長(zhǎng)。
這個(gè)時(shí)候就要引入Trie樹(shù)（前綴樹(shù)）。首先我們把字典轉(zhuǎn)化為前綴樹(shù)，這樣的好處在于它可以檢測(cè)矩陣中字母構(gòu)成的前綴是不是一個(gè)單詞的前綴，如果不是就沒(méi)必要繼續(xù)DFS下去了。這樣我們就把搜索字典中的每一個(gè)單詞，轉(zhuǎn)化為了只搜字母矩陣。代碼如下：
func findWords(_ board: [[Character]], _ dict: Set<String>) -> [String] {
var res = [String]()
let (m, n) = (board.count, board[0].count)
let trie = _convertSetToTrie(dict)
var visited = Array(repeating: Array(repeating: false, count: n), count: m)
for i in 0 ..< m {
for j in 0 ..< n {
_dfs(board, m, n, i, j, &visited, &res, trie, "")
}
}
return res
}
private func _dfs(_ board: [[Character]], _ m: Int, _ n: Int, _ i: Int, _ j: Int, inout _ visited: [[Bool]], inout _ res: [String], _ trie: Trie, _ str: String) {
// 越界
guard i >= 0 && i < m && j >= 0 && j < n else {
return
}
// 已經(jīng)訪(fǎng)問(wèn)過(guò)了
guard !visited[i][j] else {
return
}
// 搜索目前字母組合是否是單詞前綴
var str = str + "\(board[i][j])"
guard trie.prefixWith(str) else {
return
}
// 確認(rèn)當(dāng)前字母組合是否為單詞
if trie.isWord(str) && !res.contains(str) {
res.append(str)
}
// 繼續(xù)搜索上下左右四個(gè)方向
visited[i][j] = true
_dfs(board, m, n, i + 1, j, &visited, &res, trie, str)
_dfs(board, m, n, i - 1, j, &visited, &res, trie, str)
_dfs(board, m, n, i, j + 1, &visited, &res, trie, str)
_dfs(board, m, n, i, j - 1, &visited, &res, trie, str)
visited[i][j] = true
}
這里對(duì)Trie不做深入展開(kāi)，有興趣的朋友自行研究。
總結(jié)
深度優(yōu)先遍歷和廣度優(yōu)先遍歷是算法中略微高階的部分，實(shí)際開(kāi)發(fā)中，它也多與地圖路徑、棋盤(pán)游戲相關(guān)。雖然不是很常見(jiàn)，但是理解其基本原理并能熟練運(yùn)用，相信可以使大家的開(kāi)發(fā)功力更上一層樓。
