UDN-企业互联网技术人气社区

板块导航

浏览  : 435
回复  : 1

[其它] Swift 算法实战之路:深度和广度优先搜索

[复制链接]
舞操的头像 楼主
发表于 2016-8-15 19:55:54 | 显示全部楼层 |阅读模式
  之前谈到了最简单的搜索法:二分搜索。虽然它的算法复杂度非常低只有O(logn),但使用起来也有局限:只有在输入是排序的情况下才能使用。这次讲解两个更复杂的搜索算法 – 深度优先搜索(Depth-First-Search,以下简称DFS)和广度优先搜索(Breadth-First-Search,以下简称BFS)。

i.jpg


  基本概念

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

  从当前角落开始,顺着一个方向不停的找。假如这个方向全部搜索完毕依然没有找到钥匙,就回到起始角落,从另一个方向寻找,直到找到钥匙或所有方向都搜索完毕为止。这种方法就是DFS。 从当前角落开始,每次把最近所有方向的角落全部搜索一遍,直到找到钥匙或所有方向都搜索完毕为止。这种方法就是BFS。 我们假设共有10个角落,起始角落为1,它的周围有4个方向,如下图:

h.png


  DFS的搜索步骤

  1.   1

  2.   2 -> 3 -> 4

  3.   5

  4.   6 ->7 -> 8

  5.   9 -> 10
复制代码


  即每次把一个方向彻底搜索完全后,才返回搜索下一个方向。

  BFS的搜索步骤

  1.   1

  2.   2 -> 5 -> 6 -> 9

  3.   3 -> 4

  4.   7

  5.   10

  6.   8
复制代码


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

  DFS的Swift实现

  1.   func dfs(root: Node?) {

  2.   guard let root = root else {

  3.   return

  4.   }

  5.   visit(root)

  6.   root.visited = true

  7.   for node in root.neighbors {

  8.   if !node.visited {

  9.   dfs(node)

  10.   }

  11.   }

  12.   }
复制代码


  BFS的Swift实现

  1.   func bfs(root: Node?) {

  2.   var queue = [Node]()

  3.   if let root = root {

  4.   queue.append(root)

  5.   }

  6.   while !queue.isEmpty {

  7.   let current = queue.removeFirst()

  8.   visit(current)

  9.   current.visited = true

  10.   for node in current.neighbors {

  11.   if !node.visited {

  12.   queue.append(node)

  13.   }

  14.   }

  15.   }

  16.   }
复制代码


  永远记住:DFS的实现用递归,BFS的实现用循环(配合队列)。

  iOS实战演练

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

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

g.png


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

  第一步:实现字母矩阵

  首先,我们肯定有个字符二阶矩阵作为输入,姑且记做:let matrix: [[Character]]。现在要把它展现在手机上,其实很简单,就是写一个UILabel,其行数是matrix的行数,然后把matrix的每一行作为一个字符串打印在UILabel上即可。

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

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

  1.   func searchWord(board: [[Character]]) -> Bool {

  2.   guard board.count > 0 && board[0].count > 0 else {

  3.   return false

  4.   }

  5.   let m = board.count

  6.   let n = board[0].count

  7.   var visited = Array(count: m, repeatedValue: Array(count: n, repeatedValue: false))

  8.   var wordContent = [Character]("crowd".characters)

  9.   for i in 0 ..< m {

  10.   for j in 0 ..< n {

  11.   if board[i][j] == wordContent[0] && dfs(board, wordContent, m, n, i, j, &visited, 0) {

  12.   return true

  13.   }

  14.   }

  15.   }

  16.   return false

  17.   }

  18.   func dfs(board: [[Character]], _ wordContent: [Character], _ m: Int, _ n: Int, _ i: Int, _ j: Int, inout _ visited: [[Bool]], _ index: Int) -> Bool {

  19.   if index == wordContent.count {

  20.   return true

  21.   }

  22.   guard i >= 0 && i < m && j >= 0 && j < n else {

  23.   return false

  24.   }

  25.   guard !visited[i][j] && board[i][j] == wordContent[index] else {

  26.   return false

  27.   }

  28.   visited[i][j] = true

  29.   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) {

  30.   return true

  31.   }

  32.   visited[i][j] = false

  33.   return false

  34.   }
复制代码


  第三步:优化算法,进阶

  好了现在我们已经知道了怎么搜索一个单词了,那么多个单词怎么搜索?首先题目是要求找出所有的单词,那么肯定事先有个字典,根据这个字典,我们可以知道所选字母是不是可以构成一个单词。所以题目就变成了:

  已知一个字母构成的二维矩阵,并给定一个字典。选出二维矩阵中所有横向或者纵向的单词。

  也就是实现以下函数:

  1.   func findWords(board: [[Character]], _ dict: Set) -> [String] {}
复制代码


  我们刚才已经知道如何在矩阵中搜索一个单词了。所以最暴力的做法,就是在矩阵中,搜索所有字典中的单词,如果存在就添加在输出中。 这个做法显然复杂度极高:因为首先,每次DFS的复杂度就是O(n2),字母矩阵越大,搜索时间就越长;其次,字典可能会非常大,如果每个单词都搜索一遍,开销太大。这种做法的总复杂度为O(m·n2),其中m为字典中单词的数量,n为矩阵的边长。 这个时候就要引入Trie树(前缀树)。首先我们把字典转化为前缀树,这样的好处在于它可以检测矩阵中字母构成的前缀是不是一个单词的前缀,如果不是就没必要继续DFS下去了。这样我们就把搜索字典中的每一个单词,转化为了只搜字母矩阵。代码如下:

  1.   func findWords(board: [[Character]], _ dict: Set) -> [String] {

  2.   var res = [String]()

  3.   let m = board.count

  4.   let n = board[0].count

  5.   let trie = _convertSetToTrie(dict)

  6.   var visited = Array(count: m, repeatedValue: Array(count: n, repeatedValue: false))

  7.   for i in 0 ..< m {

  8.   for j in 0 ..< n {

  9.   _dfs(board, m, n, i, j, &visited, &res, trie, "")

  10.   }

  11.   }

  12.   return res

  13.   }

  14.   private func _dfs(board: [[Character]], _ m: Int, _ n: Int, _ i: Int, _ j: Int, inout _ visited: [[Bool]], inout _ res: [String], _ trie: Trie, _ str: String) {

  15.   // 越界

  16.   guard i >= 0 && i < m && j >= 0 && j < n else {

  17.   return

  18.   }

  19.   // 已经访问过了

  20.   guard !visited[i][j] else {

  21.   return

  22.   }

  23.   // 搜索目前字母组合是否是单词前缀

  24.   var str = str + "\(board[i][j])"

  25.   guard trie.prefixWith(str) else {

  26.   return

  27.   }

  28.   // 确认当前字母组合是否为单词

  29.   if trie.isWord(str) && !res.contains(str) {

  30.   res.append(str)

  31.   }

  32.   // 继续搜索上下左右四个方向

  33.   visited[i][j] = true

  34.   _dfs(board, m, n, i + 1, j, &visited, &res, trie, str)

  35.   _dfs(board, m, n, i - 1, j, &visited, &res, trie, str)

  36.   _dfs(board, m, n, i, j + 1, &visited, &res, trie, str)

  37.   _dfs(board, m, n, i, j - 1, &visited, &res, trie, str)

  38.   visited[i][j] = true

  39.   }
复制代码


  这里对Trie不做深入展开,有兴趣的朋友自行搜索。

  总结

  深度优先遍历和广度优先遍历是算法中略微高阶的部分,实际开发中,它也多与地图路径、棋盘游戏相关。虽然使用不是很常见,但是理解其基本原理并能熟练运用,相信可以使大家的开发功力更上一层楼。

原文作者:标哥 来源:开发者头条
发表于 2016-8-16 09:54:22 | 显示全部楼层
从当前角落开始,顺着一个方向不停的找。假如这个方向全部搜索完毕依然没有找到钥匙,就回到起始角落,从另一个方向寻找,直到找到钥匙或所有方向都搜索完毕为止。
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部