0. 前言

一直以来，图论相关的算法掌握就不是很好，甚至于，何时该用DFS，何时该用BFS有时都分不清。碰巧最近在刷图论相关的专题，当然作为非科班选手，掌握基础的DFS、BFS、最短路、连通块等知识，应付面试应该是够了。

在开始之前，有必要说一下DFS其实是有两种应用场景的：

搜索：此搜索一般是用于暴力递归搜索解空间，得到所有的可行解（例如回溯）
图论：在图的场景下，是对图的遍历

DFS暴力搜索

顺便记录一下DFS暴搜的过程吧，也就是所谓的回溯，模板如下：

class Gao {
    List<T> res = new ArrayList<>();    // 最终答案
    LinkedList<T> path = new LinkedList<>();    // 中间答案

    void gao() {

    }

    void back_trace() {
        if ( 条件满足 ) {
            res.add(new ArrayList(path));
            return;
        }
        // 枚举所有可能的情况
        for ( x in valids ) {
            path.add(x);        // 加入答案
            back_trace();       // 递归搜索
            path.removeLast();  // 撤销
        }
    }
    
}

最经典的问题，例如排列问题、组合问题、N皇后问题等。
例如：

LC797. 所有可能的路径

给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/all-paths-from-source-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        path = [0]
        n = len(graph)

        # x: 当前处理到的节点
        def back_trace(x):
            if x == n-1:
                res.append(path[:])
                return
            for i in range(len(graph[x])):
                path.append(graph[x][i])
                back_trace(graph[x][i])
                path.pop(-1)

        back_trace(0)
        return res

1. 二维网格问题

二维网格问题是一类特殊的图论问题。基于一个二维数组，其中，单元格可看作是node，与单元格上下左右相邻的单元格可看作是其邻居node，上下左右关系可看作是edge。

一些trick

dir 数组控制方向流转
有时初始的 grid 数组可以原地修改，作为 vis 标记和答案记录
BFS 中的队列设计，可以加入状态记录
关于从谁开始搜索：有时可以转换思路，源点和终点反过来，避免 TLE（LC 1162）
有时可以使用多源 BFS 加速搜索过程（LC 934）

DFS

网格上的DFS比较简单，如下：

LC 200. 岛屿数量

class Solution {
public:
    int res = 0;
    int numIslands(vector<vector<char>>& grid) {
        // 连通块个数
        for ( int i = 0; i < grid.size(); i++ ) {
            for ( int j = 0; j < grid[0].size(); j++ ) {
                // 标记连通块
                if ( grid[i][j] == '1' ) {
                    ++res;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    // (i, j)是坐标
    void dfs(vector<vector<char>>& g, int i, int j) {
        if ( i < 0 || i >= g.size() || j < 0 || j >= g[0].size() || g[i][j] != '1' ) return;

        g[i][j] = '2';

        dfs(g, i+1, j);
        dfs(g, i-1, j);
        dfs(g, i, j+1);
        dfs(g, i, j-1);
    }
};

BFS

使用场景

最短路径问题：基于BFS的性质，BFS首先访问的，一定是最短路
需要模拟层次扩散逻辑

LC 1091. 二进制矩阵中的最短路径

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if ( grid[0][0] == 1 || grid[n-1][n-1] == 1 ) return -1;
        int dirs[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        queue<pair<int, int>> q;
        q.push(pair(0, 0));
        // grid充当vis和答案记录
        grid[0][0] = 1;
        while ( !q.empty() ) {
            auto [x, y] = q.front();
            q.pop();
            // 当前的距离
            int dis = grid[x][y];
            for ( auto& d : dirs ) {
                int nx = d[0] + x, ny = d[1] + y;
                if ( nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] ) continue;
                grid[nx][ny] = dis + 1;
                q.push(pair(nx, ny));
            }                
        }
        return grid[n-1][n-1] == 0 ? -1 : grid[n-1][n-1];
    }
};

2. 普通图问题

一般的，图的存储实现有邻接表、邻接矩阵、链式前向星等。

需要注意的是，存储方式不同，DFS、BFS的实现也有一些不同。

DFS

大致结构

DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

BFS

BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

应用场景

在一个无权图上求从起点到其他所有点的最短路径
在一个有向无权图中找最小环（从每个点开始 BFS，在我们即将抵达一个之前访问过的点开始的时候，就知道遇到了一个环。图的最小环是每次 BFS 得到的最小环的平均值。）
在一个边权为 0/1 的图上求最短路（0-1 BFS）

大致结构

bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    // 如果要涉及到层级关系的，要把分层逻辑抽出来
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

多源BFS

前面所说的，一般都是从单个源点到单个终点的BFS，此时求最短路过程中，极其容易 TLE ，可以使用多源 BFS 加速。

LC 542. 01 矩阵

class Solution {
    public int[][] updateMatrix(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        
        // 状态描述：0 距离为0；-1,当前的“1”未访问; > 0，距离 
        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                if ( g[i][j] == 0 ) q.offer(new int[]{i, j});
                // 当前的 1 未访问
                else g[i][j] = -1;
            }
        }

        // 从所有的 0 开始多源BFS
        while ( !q.isEmpty() ) {
            int[] xy = q.poll();
            int x = xy[0], y = xy[1];
            for ( int[] d : dirs ) {
                int nx = x + d[0], ny = y + d[1];
                // 其邻居是未被访问的 1，即可确定最短距离
                if ( nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx][ny] == -1 ) {
                    g[nx][ny] = g[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }

        return g;
    }
}

LC 934. 最短的桥

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中恰好存在两座岛。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-bridge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    queue<pair<int, int>> q;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    int shortestBridge(vector<vector<int>>& grid) {
        for ( int i = 0; i < grid.size(); ++i ) {
            for ( int j = 0; j < grid[0].size(); ++j ) {
                // 将其中一个连通块标记为2 
                if ( grid[i][j] == 1 ) {
                    dfs(grid, i, j);
                    // 多源 BFS
                    return bfs(grid);
                }
            }
        }
        return 0;
    }
    // 搜索连通块
    void dfs(vector<vector<int>>& g, int i, int j) {
        if ( i < 0 || i >= g.size() || j < 0 || j >= g[0].size() || g[i][j] != 1 ) return;
        // visited
        g[i][j] = 2;
        q.emplace(make_pair(i, j));     // 直接emplace(i, j)也行
        for ( auto& d : dirs ) dfs(g, d[0]+i, d[1]+j);
    }
    int bfs(vector<vector<int>>& g) {
        int res = 0;
        while ( !q.empty() ) {
            int size = q.size();
            while ( size-- ) {
                auto [x, y] = q.front();
                q.pop();
                for ( auto& d : dirs ) {
                    int nx = x+d[0], ny = y+d[1];
                    if ( nx >= 0 && nx < g.size() && ny >= 0 && ny < g[0].size() ) {
                        if ( g[nx][ny] ==  0 ) {
                            g[nx][ny] = 2;
                            q.emplace(make_pair(nx, ny));
                        }
                        // BFS 第一个找到的，一定是最短路
                        else if ( g[nx][ny] == 1 ) return res;
                    }
                }
            }
            ++res;
        }
        return res;
    }
};

3. 二分图

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

二分图

性质

如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。
二分图不存在长度为奇数的环（因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。）

判定

红蓝染色法

LC 785. 判断二分图

class Solution {
    boolean valid = true;
    int[] color;
    int[][] g;
    public boolean isBipartite(int[][] graph) {
        color = new int[graph.length];
        g = graph;
        // 遍历每个联通分量
        for ( int i = 0; i < g.length; i++ ) {
            if ( color[i] == 0 ) {
                dfs(i, 1);
                if ( !valid ) break;
            }
        }
        return valid;
    }

    void dfs(int x, int c) {
        // 染色法判定二分图
        color[x] = c;
        for ( int next : g[x] ) {
            // 未访问，间隔染色
            if ( color[next] == 0 ) {
                dfs(next, -c);
                if ( !valid ) return;
            } else if ( color[next] == c ) {
                // 相邻节点颜色一样，必然不是二分图
                valid = false;
                return;
            }
        }
    }
}

4. 图论性质

有些题目，属于脑筋急转弯一类，可能并不需要遍历图，而是利用图的性质。

入度、出度（LC 997）
连通分量（LC 1319）
etc

算法与数据结构

DFS BFS 并查集最短路

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

数据库路由组件设计与实现上一篇

LeetCode 2022秋季编程赛总结下一篇

图论搜索模板