重温DFS&BFS

深度优先搜索

DFS（Depth-First-Search）,是盲目搜索算法的一种。常常用在树的遍历及图的处理上。假设当前搜索的节点记为k，深度优先搜索表示，继续探寻k节点的所有的边。搜索过程中，遇到满足条件的k+1节点，则继续搜索探寻k+1节点的所有的边。最后回溯至节点k。这个过程一直进行到已发现从源节点开始可以到达的所有节点位置。

广度优先搜索

BFS（Breadth-First-Search），BFS同样属于盲目搜索算法，常常使用队列（先进先出）的数据结构来辅助实现。在python中，可以使用堆栈（pop（0））的性质进行实现。BFS是从源节点开始，沿着树(图)的宽度遍历树(图)的节点。将未被访问的节点依次压入队列，再依次读取进行遍历，直到队列为空，所有节点均被访问，算法终止。

题目

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

注意点：

1. 无论DFS还是BFS，在涉及到图中上下左右搜索的问题时，一般都要建立方向数组，表示向四个方向依次遍历（dx = [-1,1,0,0]、dy = [0,0,-1,1]）
2. python中的可变对象和不可变对象传值问题。list、dict为可变对象，作为参数传递时，对象位置不发生改变。string、tuple以及int为不可变对象。

DFS算法思路：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res = 0
        if len(grid) == 0:
            return res
        m = len(grid)
        n = len(grid[0])

        mark = [[0] * n for i in range(m)]
        
        for i in range(m):
            for j in range(n):
                if mark[i][j] == 0 and grid[i][j] == '1':
                    self.dfs(mark, grid, i, j)
                    res += 1
        return res

    # 深度优先搜索:时间优于宽度优先搜索
    def dfs(self, mark, grid, x, y):
        mark[x][y] = 1
        dx = [-1, 1, 0, 0]  # 方向数组
        dy = [0, 0, -1, 1]
        m = len(grid)
        n = len(grid[0])
        # 遍历上下左右四个方向
        for i in range(4):
            newx = dx[i] + x
            newy = dy[i] + y
            if newx < 0 or newx >= m or newy >= n or newy < 0:
                continue
            if mark[newx][newy] == 0 and grid[newx][newy] == '1':
                self.dfs(mark, grid, newx, newy)



s = Solution()
nums = [['1','1',0,0,0],['1','1',0,0,0],[0,0,'1',0,'1']]
print(s.numIslands(nums))

BFS算法思路

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res = 0
        if len(grid) == 0:
            return res
        m = len(grid)
        n = len(grid[0])

        mark = [[0] * n for i in range(m)]

        for i in range(m):
            for j in range(n):
                if mark[i][j] == 0 and grid[i][j] == '1':
                    self.bfs(mark, grid, i, j)
                    res += 1
        return res

    # 深度优先搜索:时间优于宽度优先搜索
    def bfs(self, mark, grid, x, y):
        Q = []
        Q.append([x,y])
        mark[x][y] = 1
        dx = [-1, 1, 0, 0]  # 方向数组
        dy = [0, 0, -1, 1]
        m = len(grid)
        n = len(grid[0])
        # 遍历上下左右四个方向
        while Q:
            temp = Q.pop(0)
            x = temp[0]
            y = temp[1]
            for i in range(4):
                newx = dx[i]+x
                newy = dy[i]+y
                if newx < 0 or newx >= m or newy >= n or newy < 0:
                    continue
                if mark[newx][newy] == 0 and grid[newx][newy] == '1':
                    Q.append([newx, newy])  # 将新位置进入队列
                    mark[newx][newy] = 1

s = Solution()
nums = [['1','1',0,0,0],['1','1',0,0,0],[0,0,'1',0,'1']]
print(s.numIslands(nums))

参考

leetcode—200—python（深度广度优先遍历实现代码）