程序猿养成之路：DFS&BFS

2021-03-10

深度优先搜索

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍
历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。

对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。
考虑如下一颗简单的树。我们从1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，
那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为1（起
始节点）->2（遍历更深一层的左子节点）->4（遍历更深一层的左子节点）->2（无子节点，返回
父结点）->1（子节点均已完成遍历，返回父结点）->3（遍历更深一层的右子节点）->1（无子节
点，返回父结点）-> 结束程序（子节点均已完成遍历）。如果我们使用栈实现，我们的栈顶元素
的变化过程为1->2->4->3。

1

/ \

2 3

/

4

LeetCode NO.695 Max Area of Island

题目描述

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

题目分析

此题是十分标准的搜索题，我们可以拿来练手深度优先搜索。一般来说，深度优先搜索类型
的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果
可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。当然，我们也可以使用栈
（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时
笔者推荐使用递归式写法，同时也方便进行回溯。

题解

递归解法：

class Solution {
public:
    //辅助数组
    int px[4] = {-1,0,1,0};
    int py[4] = {0,-1,0,1};
    //辅函数，DFS的具体实现
    int dfs(vector<vector<int>>& grid,int x,int y){
        //递归出口
        if(grid[x][y] == 0) return 0;
        grid[x][y] = 0;
        int area = 1;
        for(int i=0;i<4;++i){
            int newx = x + px[i] , newy = y+py[i];
            if( newx >=0 && newx <grid.size() && newy>=0 && newy<grid[0].size()){
                area += dfs(grid,newx,newy);
            }
        }
        return area;
    }
	//主函数，用于遍历查找最大值
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0;
        //逐个遍历，进行DFS
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[i].size();++j){
                //比较岛屿面积
                if(grid[i][j] != 0){
                    max_area = max(dfs(grid,i,j),max_area);
                }
            }
        }
        return max_area;
    }
};

迭代写法：（利用栈）

class Solution{
public:
    int px[4] = {-1,0,1,0};
    int py[4] = {0,-1,0,1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[i].size();++j){ //遍历数组
                if(grid[i][j] != 0){ 	//为1，开始入栈出栈
                    grid[i][j] = 0;
                    int area = 0;
                    stack<pair<int,int>> s;
                    s.push({i,j});
                    while(!s.empty()){	//栈不为空的情况下循环
                        int x = s.top().first;
                        int y = s.top().second;
                        s.pop();
                        ++area;
                        for(int i=0;i<4;++i){ //查找临近节点，为1则入栈
                            int newx = x+px[i];
                            int newy = y+py[i];
                            if(newx >=0 && newx < grid.size() 
                                && newy >= 0 && newy <grid[0].size() && grid[newx][newy] != 0){
                                    grid[newx][newy] = 0;
                                    s.push({newx,newy});
                                    
                            }
                        }
                    }
                    max_area = max(max_area,area);
                }
            }
        }
        return max_area;
    }
};

LeetCode NO.547 Number of Provinces

题目描述

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

题解

class Solution {
public:
    //dfs要完成的任务：遍历一行情况
    void dfs(vector<vector<int>>& isConnected,int i,vector<bool>& visit){
        visit[i] = true;
        for(int j=0;j<isConnected[0].size();++j){
            if(isConnected[i][j]==1 && visit[j]==false){
                dfs(isConnected,j,visit);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        //对某市的邻接情况进行遍历
        int count = 0;
        vector<bool> visit(isConnected.size(),false);
        for(int i = 0;i<isConnected.size();++i){
            if(!visit[i]){
                dfs(isConnected,i,visit);
                ++count;  
            } 
        }
        return count;
    }
};

LeetCode NO.417 Pacific Atlantic Water Flow

题目描述

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5)
~ 3 2 3 (4) (4)
~ 2 4 (5) 3 1
~ (6) (7) 1 4 5
~ (5) 1 1 2 4 *
      *   *   *   *   * Atlantic
Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

题解

使用两个bool型数组来判断该点能否流到太平洋，最后合并数组，同时为true的节点放入返回数组中。

第一种解法是由高点出发向低点搜索，但是存在大量的重复计算。

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    pair<bool,bool> dfs(vector<vector<int>>& matrix,int x ,int y,vector<vector<bool>>& visited){
        if(x == -1 || y== -1)  {
            return pair<bool,bool>(true,false);
        }
        if(x == matrix.size() || y ==matrix[0].size()){
            return pair<bool,bool>(false,true);
        }
        //递归访问标记
        visited[x][y] = true;
        //用pair存储返回值
        pair<bool,bool> res;
        //递归到邻接节点
        for(int i=0;i<4;++i){
            int newx = x+dir[i],newy = y+dir[i+1];
            //递归前要判断以下，如果是边界则直接递归，如果不是要判断下一步的高度才能决定能否递归
            if( newx ==-1 || newx==matrix.size() || newy==-1 || newy == matrix[0].size()){
                pair<bool,bool> temp = dfs(matrix,newx,newy,visited);
                res.first = temp.first || res.first;
                res.second = temp.second || res.second;
            }
            else if(matrix[newx][newy] <= matrix[x][y] && !visited[newx][newy]){
                pair<bool,bool> temp = dfs(matrix,newx,newy,visited);
                res.first = temp.first || res.first;
                res.second = temp.second || res.second;
            }
        }
        return res;
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if(matrix.empty()) return {}; 
        //辅助数组，记录每个点能否流到海洋
        int m = matrix.size(),n = matrix[0].size();
        vector<vector<bool>> pac(m,vector<bool>(n,false));
        vector<vector<bool>> alt(m,vector<bool>(n,false));
        //遍历每个节点
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                vector<vector<bool>> visited(m,vector<bool>(n,false));
                pair<bool,bool> result = dfs(matrix,i,j,visited);
                pac[i][j] = result.first;
                alt[i][j] = result.second;
            }
        }
        //只有两个数组都为true才行
        vector<vector<int>> res;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(pac[i][j] && alt[i][j])
                    res.push_back({i,j});
            }
        }
        return res;
    }
};

第二种解法由低向高进行DFS，这样边搜索边记录，简化了搜索流程。

class Solution {
public:
	vector<int> dir{-1,0,1,0,-1};
    void dfs(vector<vector<int>>& matrix,int x,int y,vector<vector<bool>>& visited){
        //访问标记
        visited[x][y] = true;
        //递归调用
        for(int i=0;i<4;++i){
            int newx = x +dir[i],newy = y+dir[i+1];
            if(newx>=0 && newx <matrix.size() && newy>=0 &&newy <matrix[0].size()
            && matrix[newx][newy]>=matrix[x][y] && !visited[newx][newy]){
                dfs(matrix,newx,newy,visited);
            }
        }
    }


    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix){
        if(matrix.empty()) return {};
        int m = matrix.size(),n = matrix[0].size();
        //从低到高遍历
        vector<vector<bool>> pac(m,vector<bool>(n,false));
        vector<vector<bool>> alt(m,vector<bool>(n,false));
        for(int i=0;i<m;++i){
            dfs(matrix,i,0,pac);
            dfs(matrix,i,n-1,alt);
        }
        for(int j=0;j<n;++j){
            dfs(matrix,0,j,pac);
            dfs(matrix,m-1,j,alt);
        }
        vector<vector<int>> result;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(pac[i][j] && alt[i][j]){
                    result.push_back({i,j});
                }
            }
        }
        return result;
    }
};

回溯法

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。

顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。在具体的写法上，它与普通的深度优先搜索一样，都有[修改当前节点状态]->[递归子节点] 的步骤，只是多了回溯的步骤，变成了[修改当前节点状态]->[递归子节点]->[回改当前节点状态]。

回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

LeetCode NO.46 Permutations

题目描述

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

题解

使用数组来记录和标记状态，对每一位进行填充，如果当前数字已经被使用，则跳过；如果没有被使用则填充进去，进行下一个位置的填充。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<bool> used(n,false);
        vector<vector<int>> res;
        vector<int> temp;
        backtrack(nums,0,res,temp,used);
        return res;
    }
    void backtrack(vector<int>& nums,int curr,vector<vector<int>>& res,vector<int>& temp,vector<bool>& used){
        //递归终止条件
        if(curr == nums.size()){
            res.push_back(temp);
            return;
        }

        //填入第curr个位置
        for(int i=0;i<nums.size();++i){
            if(!used[i]){
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums,curr+1,res,temp,used);
                used[i] = false;
                temp.pop_back();
            }
        }
    }
};

交换写法

class Solution{
	void backtrack(vector<int>& nums,int curr ,vector<vector<int>>& res){
        //递归出口
        if(curr == nums.size()){
            res.push_back(nums);
            return;
        }
        //填充第curr位——交换
        for(int i=curr;i<nums.size();++i){
            swap(nums[i],nums[curr]);
            backtrack(nums,curr+1,res);
            swap(nums[i],nums[curr]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(nums,0,res);
        return res;
    }
};

LeetCode NO.77 Combinations

题目描述

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20
1 <= k <= n

题解

class Solution {
public:
    void backtrack(vector<vector<int>>& res,vector<int>& temp,int n,int k,int curr){
        if(temp.size() == k){
            res.push_back(temp);
            return;
        }
        for(int i=curr;i<=n;i++){
            temp.push_back(i);
            backtrack(res,temp,n,k,i+1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> temp;
        backtrack(res,temp,n,k,1);
        return res;
    }
};

广度优先搜索

广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因
此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时
按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。
考虑如下一颗简单的树。我们从1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，
那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为[1]->[2->3]->[4]，其中
方括号代表每一层的元素。

1

/ \

2 3

/

4

这里要注意，深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否
能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索
刷此类题目。实际软件工程中，笔者很少见到递归的写法，因为一方面难以理解，另一方面可能
产生栈溢出的情况；而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太
大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。

LeetCode NO.934 Shortest Bridge

题目描述

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: A = [[0,1],[1,0]]
Output: 1

Example 2:

Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

题目分析

本题实际上是求两个岛屿间的最短距离，因此我们可以先通过任意搜索方法找到其中一个岛
屿，然后利用广度优先搜索，查找其与另一个岛屿的最短距离。

题解

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    void dfs(vector<vector<int>>& A,int x,int y,queue<pair<int,int>>& q){
        if(x<0 || y<0 || x == A.size() || y==A[0].size() || A[x][y] == 2){
            return;
        }
        else if(A[x][y] == 0){
            q.push({x,y});
            return;
        }
       
        A[x][y] = 2;
        for(int i=0;i<4;++i){
            int newx = x+dir[i],newy = y+dir[i+1];
            dfs(A,newx,newy,q);
        }
    }
    int shortestBridge(vector<vector<int>>& A) {
        int m = A.size(),n = A[0].size();
        queue<pair<int,int>> q;
        bool flipped = false;
        for(int i=0;i<m;++i){
            if(flipped) break;
            for(int j=0;j<n;++j){
                if(A[i][j]==1){
                    dfs(A,i,j,q);
                    flipped = true;
                    break;
                }
            }
        }
        int step = 0;
        while(!q.empty()){
            ++step;
            int size = q.size();
            while(size--){
                auto [x,y] = q.front();
                q.pop();
                A[x][y] = 2;
                //周围节点入队列
                for(int j=0;j<4;++j){
                    int newx = x+dir[j],newy = y+dir[j+1];
                    if(newx<0 || newx == m || newy<0 || newy==n || A[newx][newy] == 2){
                        continue;
                    }
                    else if(A[newx][newy] == 0 ){
                        A[newx][newy] = 2;
                        q.push({newx,newy});
                    }
                    else if(A[newx][newy] == 1){
                        return step;
                    }
                }
            }
            
        }
        return -1;
    }
};