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

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看126 回复回复1 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 126|回复: 1
收起左侧

[中文教程] Swift 算法实战之路:深度和广度优先搜索

[复制链接]
代码买卖 发表于 2016-9-7 03:35:14 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
本帖最后由 代码买卖 于 2016-9-7 05:24 编辑


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

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

Swift 算法实战之路:深度和广度优先搜索 - 敏捷大拇指 - Swift 算法实战之路:深度和广度优先搜索 0





1、基本概念

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

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


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

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

Swift 算法实战之路:深度和广度优先搜索 - 敏捷大拇指 - Swift 算法实战之路:深度和广度优先搜索 1


DFS的搜索步骤为:

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


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

BFS的搜索步骤为:

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


即每次访问上一步周围所有方向上的角落

细心的朋友会记得,我之前在讲二叉树的时候,讲到了前序遍历和层级遍历,而这两者本质上就是DFS和BFS。



1.1、DFS的Swift实现:

[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)
        }
    }

}




1.2、BFS的Swift实现:

[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的实现用循环(配合队列)。




2、iOS实战演练

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

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


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

Swift 算法实战之路:深度和广度优先搜索 - 敏捷大拇指 - Swift 算法实战之路:深度和广度优先搜索 2

找单词App

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



2.1、第一步:实现字母矩阵

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

[Swift] 纯文本查看 复制代码
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
}




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

现在要实现搜索单词的核心算法了。我们先简化要求,假如只在字母矩阵中搜索单词"crowd"该怎么做?

首先我们要找到 "c" 这个字母所在的位置,然后再上下左右找第二个字母 "r" ,接着再找字母 "o" 。。。以此类推,直到找到最后一个字母 "d" 。如果没有找到相应的字母,我们就回头去首字母 "c" 所在的另一个位置,重新搜索。

这里要注意一个细节,就是我们不能回头搜索字母。比如我们已经从 "c" 开始向上走搜索到了 "r" ,这个时候就不能从 "r" 向下回头 —— 因为 "c" 已经访问过了。所以这里需要一个var visited: [[Bool]] 来记录访问记录。代码如下:

[Swift] 纯文本查看 复制代码
func searchWord(board: [[Character]]) -> Bool {
    guard board.count > 0 && board[0].count > 0 else {
        return false
    }

    let m = board.count
    let n = board[0].count
    var visited = Array(count: m, repeatedValue: Array(count: n, repeatedValue: false))
    var wordContent = [Character]("crowd".characters)

    for i in 0 ..< m {
        for j in 0 ..< n {
            if board[i ][j] == wordContent[0] && 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, inout _ visited: [[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
}




2.3、第三步:优化算法,进阶

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

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


也就是实现以下函数:

[Swift] 纯文本查看 复制代码
func findWords(board: [[Character]], _ dict: Set<String>) -> [String] {}


我们刚才已经知道如何在矩阵中搜索一个单词了。所以最暴力的做法,就是在矩阵中,搜索所有字典中的单词,如果存在就添加在输出中。

这个做法显然复杂度极高:首先,每次DFS的复杂度就是O(n^2),字母矩阵越大,搜索时间就越长;其次,字典可能会非常大,如果每个单词都搜索一遍,开销太大。这种做法的总复杂度为O(m·n^2),其中m为字典中单词的数量,n为矩阵的边长。

这个时候就要引入Trie树(前缀树)。首先我们把字典转化为前缀树,这样的好处在于它可以检测矩阵中字母构成的前缀是不是一个单词的前缀,如果不是就没必要继续DFS下去了。这样我们就把搜索字典中的每一个单词,转化为了只搜字母矩阵。代码如下:

[Swift] 纯文本查看 复制代码
func findWords(board: [[Character]], _ dict: Set<String>) -> [String] {
  var res = [String]()

  let m = board.count
  let n = board[0].count

  let trie = _convertSetToTrie(dict)
  var visited = Array(count: m, repeatedValue: Array(count: n, repeatedValue: false))

  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
  }

  // 已经访问过了
  guard !visited[i ][j] else {
    return
  }

  // 搜索目前字母组合是否是单词前缀
  var str = str + "\(board[i ][j])"
  guard trie.prefixWith(str) else {
    return
  }

  // 确认当前字母组合是否为单词
  if trie.isWord(str) && !res.contains(str) {
    res.append(str)
  }

  // 继续搜索上下左右四个方向
  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
}


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




3、总结

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

下一篇我们讨论Swift动态规划




相关内容

Swift 算法实战之路:基本语法与技巧

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:链表

Swift 算法实战之路:栈和队列

Swift 算法实战之路:二叉树

Swift 算法实战之路:排序

Swift 算法实战之路:二分搜索

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

Swift 算法实战之路:动态规划




作者:故胤道长

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

我是90后 发表于 2016-9-7 22:54:01 | 显示全部楼层
Nice~~~~~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
关闭

站长推荐 上一条 /3 下一条

热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表