力扣刷题笔记 #06 图论

本文包含「图论」类型题中的：遍历图、矩阵图模拟、拓扑排序、最短路、最小生成树、网络流等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

图的表示通常有：邻接矩阵、邻接表（数组或链表）、链式前向星。在这里提到的「图」通常以邻接表数组存储。

遍历图

BFS & DFS，遍历图比遍历树麻烦，需要防止多次访问同一个节点，陷入死循环。通常是采用哈希表或哈希集合存储访问过的点，下次访问时判断即可。

常用有向图代码：

// 一维数组 nums 存点, 二维数组 edges 存边
vector<vector<int>> g(nums.size());
vector<int> in(nums.size()), out(nums.size());
for (auto &e : edges) {
    g[e[0]].push_back(e[1]); // 有向图，只存一次
    in[e[1]]++, out[e[0]++];
}

常用无向图代码：

// 一维数组 nums 存点, 二维数组 edges 存边
vector<vector<int>> g(nums.size());
for (auto &e : edges) {
    int x = e[0], y = e[1];
    g[x].push_back(y);
    g[y].push_back(x); // 无向图，存两次
}

133. 克隆图 (M)

题目描述：给出无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆），原图以链式邻接表存储。

方法1：DFS，用哈希表 \(vis\) 记录 node 和 cloneNode 的映射关系，同时标记访问过的节点，当遇到重复节点时直接返回哈希表中的记录。递归调用主函数，遍历邻接表中的所有点。时间复杂度 \(O(n)\)。

方法2：BFS，哈希表 \(vis\) 和方法 1 类似，使用一个队列来存放即将遍历的点，时间复杂度 \(O(n)\)。

矩阵图模拟

给定一个矩阵，矩阵上的点可以视为四向连通的图节点（除边界外）。常见的有岛屿问题、火势蔓延问题等。常用技巧：

• 采用 DFS 遍历时，终止的条件之一为数组下标越界，可以独立一个 valid 函数判断。
• 全局定义四个方向，然后再用 for(auto &d : dir) 循环。
• 矩阵中的连通块可以用不同的数字标记（在一个等大的数组中），再用哈希表记录数字对应的属性。
• 用数字记录连通块还有一个好处：在特定时候可以用 set<int> 去重、或者判断是否已经可达。

常用代码段：

// 在全局定义
int n, m;
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool valid(int row, int col){
    return row >= 0 && row < n && col >= 0 && col < m;
}
// 记忆化搜索，传入矩阵 + 记忆化数组 + 当前坐标
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& vis, int x, int y){
    vis[x][y] = true;
    for(auto &d : dir){
        int nx = x + d[0], ny = y + d[1];
        if(valid(nx, ny) && grid[nx][ny] == '1' && !vis[nx][ny]){
            dfs(grid, vis, nx, ny);
        }
    }
    return ;
}
// 主函数
int main(vector<vector<char>>& grid){
    n = grid.size(), m = grid[0].size();
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    // TODO
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == '1' && !vis[i][j]){
                // TODO
                dfs(grid, vis, i, j);
            }
        }
    }
}

200. 岛屿数量 (M)

题目描述：给定 \(m\times n\) 矩阵，矩阵上的 \(1\) 代表陆地，\(0\) 代表海洋，计算网格中岛屿的数量。

方法1：DFS，遍历矩阵，当遇到陆地时 DFS 标记整个岛屿访问过的点，时空复杂度均为 \(O(mn)\)。

方法2：并查集，相邻的 \(1\) 合并到同一个集合，遍历每个 \(0\)，最终答案就是并查集中连通分量的数目。时间复杂度为 \(O(mn \times \alpha(mn))\)。

130. 被围绕的区域 (M)

题目描述：：给定 \(m\times n\) 矩阵，由字符 X 和 O 构成，找到所有被 X 包围的 O，并将其替换为 X。

方法：DFS，已知没有被 X 包围的 O 必然与边界相连，因此从边界上的 O 开始 DFS 搜索，可以找到最终保留的 O。将所有保留的 O 替换成临时字母 A，最后将剩余 O 修改为 X，再将 A 恢复即可。

934. 最短的桥 (M)

题目描述：给定 \(n\times n\) 矩阵，矩阵上的 \(1\) 代表陆地，\(0\) 代表海洋，网格中恰好有两座岛，可以将任意数量的 \(0\) 修改为 \(1\)，计算最少的修改次数。

方法1：先 DFS 标记第一个岛，并将其周围的一圈水域入队，再进行记忆化 BFS，搜索水域并记录路径长度，直到搜索到第二个岛，时间复杂度 \(O(n^2)\)。

方法2：双向 BFS，用 DFS 先标记两个岛，用两个队列分别存储两个岛周围的水域，每次从队列较小的进行扩展，比方法 1 更快一些。

827. 最大人工岛 (H)

题目描述：给定 \(n\times n\) 矩阵，矩阵上的 \(1\) 代表陆地，\(0\) 代表海洋，最多可将一个 \(0\) 变成 \(1\)，返回可能的最大岛屿面积。

方法1：DFS，第一次遍历用不同的数字标记岛屿，再用哈希表统计每个数字对应的面积。第二次遍历所有 \(0\)，将海洋的四个方向的岛屿面积相加。时空复杂度均为 \(O(n^2)\)。

方法2：并查集，相邻的 \(1\) 合并到同一个集合，遍历每个 \(0\)，查找其相邻四个点所在集合，累加去重后的岛屿面积。时间复杂度为 \(O(n^2 \alpha(n^2 ))\)。

Todo水位上升

拓扑排序

拓扑排序发生在有向无环图（DAG）中，存在两种线性时间算法：

• 入度表 BFS：用一个数组存储入度，将 0 入度的点放入队列，依次删除队列中的点，删除后再找 0 入度的点，删除顺序即为拓扑排序。
• DFS 判圈：用一个访问数组存储三种状态：未访问、已访问、已入栈，用栈来保存拓扑排序的顶点序列。
  • 从任意一个未访问过的点开始 DFS，先标记为已访问，再遍历 DFS 邻接点。
  • 如果遍历到的邻接点也是已访问的状态，则找到环；否则在遍历 DFS 完所有邻接点后该点入栈。
  • 保证在某顶点入栈前，其所有邻接点已入栈，栈顶到栈底即为拓扑排序。

207. 课程表 (M)

题目描述：给定 \(n\) 门课程，以及课程之间的先修关系，判断是否可能完成所有课程的学习。

方法1：入度表 BFS，存储有向图时记录每个节点的入度，将入度为 \(0\) 的点放入队列，依次将队列里的每个节点删除（实际只要将其指向的点入度减一），并将入度变为 \(0\) 的点也放入队列。时间复杂度 \(O(V+E)\)。

方法2：DFS 判圈，有向无环图一定存在拓扑排序，因此只要判断图中是否有圈。用 \(vis\) 数组记录三种状态，时间复杂度 \(O(V+E)\)。

329. 矩阵中的最长递增路径 (H)

题目描述：给定 \(m\times n\) 整数矩阵，每个单元格可以往四个方向移动，找出其中最长递增路径的长度。

方法1：矩阵图模拟 + 记忆化搜索，DFS 终止条件是相邻点没有更大值，否则就先 DFS 求出邻居的结果。用 vis 数组记录访问过的点，每次 DFS 时剪枝，时空复杂度均为 \(O(mn)\)。

方法2：拓扑 + 入度表 BFS，把矩阵看作一个有向图，有向边从较小数指向较大数，问题转化为「求图中最长路径」，从所有出度为零的点开始 BFS，当搜索结束（队列空）时搜索的层数即为答案。时间复杂度为 \(O(V+E)\approx O(mn)\)。

最短路问题

最短路问题通常出现在带权图中，分为单源最短路（SSSP）和全源最短路（APSP）。前者包括 Dijkstra（无法处理负权）、Bellman-Ford（可以处理负权，支持负圈检测）、DAG SSSP、SPFA 算法。后者常用 Floyd-Warshall 算法。注意，最短路算法适用于有向图和无向图，只是在建图时用单向边或双向边的区别。

Dijksta 的关键操作在于「松弛」，即对新加入顶点的可达顶点进行更新，使用了贪心思想。此外，\(getMin\) 操作可以用堆优化，适合边较少的稀疏图，复杂度 \(O(E\log E)\)。堆优化模板如下：

typedef pair<int, int> pii;
// 建图
vector<vector<pii>> g(n); // n 是顶点数
for (auto &e: edges) {
    int u = e[0], v = e[1], w = e[2];
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w); // 建无向图，有向图需删掉
}
// Dijkstra 算法，返回从 start 到每个点的最短路
vector<int> dist(n, INT_MAX); // 初始所有节点都不可达
dist[start] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq; // {距离, 目标点} 先按距离排序
pq.emplace(0, start);
while (!pq.empty()) {
    auto [d, x] = pq.top();
    pq.pop();
    if (d > dist[x]) continue; // 堆里存的可能是已经访问过的点，这里相当于 vis
    for (auto &[y, wt] : g[x]) {
        int new_d = dist[x] + wt;
        if (new_d < dist[y]) {
            dist[y] = new_d;
            pq.emplace(new_d, y); // 将可达点放入堆，等待访问
        }
    }
}

Floyd 算法的本质也是贪心，常用邻接矩阵存图，最终矩阵中就是两两间的最短路，时间复杂度 \(O(V^3)\)，模板如下：

const int inf = 0x3f3f3f3f;
vector<vector<int>> g(n, vector<int>(n, inf));
for(int i = 0; i < n; i++) g[i][i] = 0; // 到自身的距离为 0
for (auto &e: edges) {
    int u = e[0], v = e[1], w = e[2];
    g[u][v] = w;
    g[v][u] = w; // 建无向图，有向图需删掉
}
// Floyd 算法，k 为中间点，最终 g 中存储两两间的最短路
for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
    }
}

743. 网络延迟时间 (M)

题目描述：给定一个有向带权图，权重表示信号经过边的传递时间，求从节点 \(k\) 发出信号后多久，所有节点都能收到。

方法：单源最短路，用 Dijkstra 找出距离节点 \(k\) 最远的点，则该点收到信号时就是所有点都能收到信号。时间复杂度 \(O(E\log E )\)。

坑点：\(n\) 个节点的编号 \([1,n]\)，建图时最好手动转为 \([0,n-1]\)，否则会多一个不可能到达的节点 \(0\)。

882. 细分图中的可到达节点 (H)

题目描述：给定一个无向图，现在将每条边分裂出 \(cnt_i\) 个细分点，得到新的一个细分图。计算此时从节点 \(0\) 出发，经过 \(maxMoves\) 步可以到达的节点数。

方法：单源最短路，边上的细分点 \(cnt_i+1\) 可以看作边的权重，用 Dijkstra 先在原图中找出起点能到达的所有顶点。对顶点 \(u\) 而言，到达后还剩的步数记为 \(resU\)。则枚举所有边 \((u,v)\)，其上的细分点最多能访问 \(\max(resU+resV, cnt)\) 个。时间复杂度 \(O(E\log E)\)。

Todo 1334. 阈值距离内邻居最少的城市 (M)

题目描述：

方法1：全源最短路

方法2：

方法3：

1631. 最小体力消耗路径 (M)

题目描述：

方法1：

方法2：

方法3：

Todo 407. 接雨水 II (H)

题目描述：

方法1：

方法2：

方法3：

坑点：

最小生成树

两大算法：Prim（类似 Dijk）& Kruskal（并查集）。

int prim(vector<vector<int> >& points, int start) {
    int n = points.size();
    int res = 0;

    // 1. 邻接矩阵
    vector<vector<int> > g(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            g[i][j] = g[j][i] = dist;
        }
    }
    // 记录V中的点到Vnew的最近距离
    vector<int> lowcost(n, INT_MAX);
    // 记录V中的点是否加入到了Vnew
    vector<int> v(n);
    // lowcost 和 v 可以优化成一个数组

    // 2. 先将start加入到Vnew
    v[start] = 1;
    for (int i = 0; i < n; i++) {
        if (i == start) continue;
        lowcost[i] = g[i][start];
    }

    // 3. 遍历剩余若干个未加入到Vnew的节点
    for (int _ = 1; _ < n; _++) {
        // 找出此时V中，离Vnew最近的点
        int minIdx = -1;
        int minVal = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (v[j] == 0 && lowcost[j] < minVal) {
                minIdx = j;
                minVal = lowcost[j];
            }
        }
        // 将最近的点加入Vnew
        v[minIdx] = 1;
        res += minVal;

        // 更新集合V中剩余所有点的lowcost
        for (int j = 0; j < n; j++) {
            if (v[j] == 0 && g[j][minIdx] < lowcost[j]) {
                lowcost[j] = g[j][minIdx];
            }
        }
    }
    return res;
}

连通性问题

Tarjan 算法是基于 DFS 的算法，可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的双连通分量；同时，也可以求解有向图的强连通分量、必经点与必经边。

https://zhuanlan.zhihu.com/p/101923309

网络流

最大流最小割定理。