BFS

BFS指的是宽度优先遍历

  1. 利用队列实现，从源节点开始依次按照宽度进队列，然后弹出
  2. 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
  3. 直到队列变空

举一个例子，以二叉树的层序遍历为例，先将头节点放入队列中，然后弹出，弹出时将左右节点依次放入队列中，重复以上操作。若需要按照层序划分，可以维护一个当前层级的变量curLevel：在下一层的层级为curLevel+1，当队列弹出的节点出现新的层级时说明进入新的一层，而此时整个队列包含的元素均为同一层的节点。

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<vector<int> > levelOrderBottom(TreeNode *root)
{
    vector<vector<int> > res;
    if (root == nullptr)
        return res;
    queue<pair<TreeNode *, int> > q;
    int curLevel = 0;
    q.push(make_pair(root, curLevel));
    vector<int> tmp;
    while (!q.empty())
    {
        pair<TreeNode *, int> cur = q.front();
        q.pop();
        if (cur.second == curLevel)
            tmp.push_back(cur.first->val);
        else
        {
            curLevel++;
            res.push_back(tmp);
            tmp.clear();
            tmp.push_back(cur.first->val);
        }
        if (cur.first->left != nullptr)
            q.push(make_pair(cur.first->left, curLevel + 1));
        if (cur.first->right != nullptr)
            q.push(make_pair(cur.first->right, curLevel + 1));
    }
    res.push_back(tmp);
    return res;
}

补充：但其实这个问题有更简单的解决方案，那就是利用队列的size来进行一次性录入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
    }

    return res;
}

其对应的题目包括：

  1. 102. Binary Tree Level Order Traversal
  2. 116. Populating Next Right Pointers in Each Node
  3. 130. Surrounded Regions
  4. 399. Evaluate Division
  5. 542. 01 Matrix【累计距离】

img

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

此题很有价值，处理的方法很简单：我们在进行广度优先搜索的时候会使用到队列，在只有一个 0 的时候，我们在搜索前会把这个 0的位置加入队列，才能开始进行搜索；如果有多个 0，我们只需要把这些 0 的位置都加入队列就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
            }
        }
        // 广度优先搜索
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }
        return dist;
    }
};
  1. 752. Open the Lock【累计距离】
1
2
3
4
5
6
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

我们可以使用广度优先搜索，找出从初始数字 00000000 到解锁数字 \textit{target}target 的最小旋转次数。

具体地，我们在一开始将 (0000, 0)(0000,0) 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的数字为 status，旋转的次数为 step，我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为next_status，如果其没有被搜索过，我们就将(next_status,step+1) 加入队列。如果搜索到了 target，我们就返回其对应的旋转次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<pair<string,int>> q;
        unordered_set<string> word_set;
        for(string deadend:deadends){
            word_set.insert(deadend);
            if(deadend=="0000")return -1;
        }
        q.push({"0000",0});
        while(!q.empty()){
            int n=q.size();
            for(int i =0;i<n;i++){
                auto tmp=q.front();q.pop();
                if(tmp.first==target)return tmp.second;
                for(int j=0;j<4;j++){
                    tmp.first[j]=(tmp.first[j]-'0'+10+1)%10+'0';
                    if(word_set.find(tmp.first)==word_set.end()){
                        word_set.insert(tmp.first);
                        q.push({tmp.first,tmp.second+1});//将上一个节点的距离拿出来，加一再存入下一个节点的写法非常重要
                    }
                    tmp.first[j]=(tmp.first[j]-'0'+10-2)%10+'0';
                    if(word_set.find(tmp.first)==word_set.end()){
                        word_set.insert(tmp.first);
                        q.push({tmp.first,tmp.second+1});
                    }
                    tmp.first[j]=(tmp.first[j]-'0'+10+1)%10+'0';
                }
            }
        }
        return -1;
    }
};

经典题目：BFS、DFS、并查集通解

547. Number of Provinces

img

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

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> visited(n);
        queue<int> q;
        int count=0;
        for(int i=0;i<n;i++){
            if(visited[i]==0){
                count++;
                visited[i]=1;
                q.push(i);//首先让一个节点入队列
                while(!q.empty()){
                    int j=q.front();q.pop();
                    for(int k=0;k<n;k++){
                        if(isConnected[j][k]==1&&visited[k]==0){//所有与此节点相连的节点，如果满足调节则也入队
                            visited[k]=1;
                            q.push(k);
                        }
                    }
                }
            }
        }
        return count;
    }
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, vector<int>& visited,int i,int n){
        for(int j=0;j<n;j++){
            if(isConnected[i][j]==1&&visited[j]==0){//沿着这个节点
                visited[j]=1;
                dfs(isConnected,visited,j,n);//继续寻找符合条件的节点
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int count =0;
        int n=isConnected.size();
        vector<int> visited(n,0);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(isConnected[i][j]==1 && visited[i]==0){
                    visited[i]=1;
                    count++;
                    dfs(isConnected,visited,i,n);//先找到一个满足条件的节点
                }
            }
        }
        return count;
    }
};

Union Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        int count = n;
        unordered_map<int,int> mp(n);
        for(int i=0;i<n;i++){
            mp[i]=i;//每个节点首先都指向自己
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(isConnected[i][j]==1){//注意，i和j是相连的
                    int root1=i;
                    while(mp[root1]!=root1)root1=mp[root1];//找到根节点
                    int root2=j;
                    while(mp[root2]!=root2)root2=mp[root2];
                    if(root1!=root2){//将两个相连的根统一起来
                        mp[root1]=root2;
                        count--;//找到一组相连的点，删掉一个
                    }
                }
            }
        }
        return count;
    }
};

785. Is Graph Bipartite?

img

1
2
3
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int UNCOLORED=0;//首先定义未染色
        int RED=1;//一种颜色为红色
        int GREEN=2;//一种颜色为绿色
        int n =graph.size();
        vector<int> color(n,UNCOLORED);//初始化所有颜色为未染色
        for(int i =0;i<n;i++)//按照编号遍历
        {
            if(color[i]==UNCOLORED)//如果未染色，
            {
                queue<int> q;
                color[i]=RED;//先染成红色
                q.push(i);//放到队列里面
                while(!q.empty())
                {
                    int temp=q.front();
                    q.pop();
                    int colorNeighbor = (color[temp]==RED?GREEN:RED);//给邻居染上另一种颜色
                    for(int j: graph[temp])
                    {
                        if(color[j]==UNCOLORED)//如果邻居是未染色则染上另一种颜色
                        {
                            color[j]=colorNeighbor;
                            q.push(j);
                        }
                        else if(color[j]!=colorNeighbor)//如果邻居的颜色和自身相同，则说明不能实现二分图
                            return false;
                    }
                }
            }
        }
        return true;
    }
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;
    vector<int> color;
    bool valid;

public:
    void dfs(int node, int c, const vector<vector<int>>& graph) {
        color[node] = c;//首先染成红色
        int cNei = (c == RED ? GREEN : RED);//得到邻居颜色
        for (int neighbor: graph[node]) {
            if (color[neighbor] == UNCOLORED) {//对于未染色的邻居
                dfs(neighbor, cNei, graph);//以规定的邻居颜色进行染色
                if (!valid) {//如果染色有问题则返回
                    return;
                }
            }
            else if (color[neighbor] != cNei) {//如果邻居与自身同色
                valid = false;
                return;
            }
        }
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        valid = true;
        color.assign(n, UNCOLORED);
        for (int i = 0; i < n && valid; ++i) {
            if (color[i] == UNCOLORED) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }
};