图算法总结

概述

编程的通用模式：

1. 问题理解和建模。
2. 分解子问题，简化复杂度。
3. 逐个解决子问题，解决主问题。

本文尝试用尽量短的文字概况问题的核心，总结LeetCode中图算法题目。

经典图算法

图的搜索

1. DFS（深度优先搜索）

void bfs(vector<vector<int>>& G, vector<bool>& seen, int u) {
	if (减枝条件) {
		return;
	}
	if (满足答案) {
		// 记录结果
		return;
	}
	
	// 访问节点u
	seen[u] = true;
	for (int v: G[u]) {
		// 访问边 u->v
		dfs(G, seen, v);
		// 回溯边 u->v
	}
	// 回溯节点u
	seen[u] = false;
}

1. BFS（广度优先搜索）

void bfs(vector<vector<int>>& G, int src) {
    queue<int> q;
	vector<bool> seen(G.size());
	q.push(src);
	seen[src] = true;
	int level = 0;
    while (!q.empty()) {
        int n = q.size();
		for (int i = 0; i < n; i++) {
			int u = q.front();
			q.pop();
			for (int v: G[u]) {
				if (!seen[v]) {
					q.push(v);
					seen[v] = true;
				}
			}
		}
		level++;
    }
}

最短路径

单源最短路径Dijkstra

vector<int> dijkstra(vector<vector<pair<int, int>>> &G, int s) {
    vector<int> dist(G.size(), INT_MAX);
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, s);

    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du > dist[u])
            continue;
        for (auto &[v, dv] : G[u]) {
            int d = dist[u] + dv;
            if (dist[v] > d) {
                dist[v] = d;
                pq.emplace(d, v);
            }
        }
    }

    return dist;
};

最小生成树

1. Kruskal算法

vector<vector<int>> kruskal(vector<vector<int>>& edges) {
    sort(edges.begin(), edges.end(),
         [](auto &u, auto &v) { return u[2] < v[2]; });
    UnionFind fa(n);
    vector<vector<int>> tree;
    for (auto &e : edges) {
        if (fa.unite(e[0], e[1])) {
            tree.push_back(e);
        }
    }

    return tree;
}

计算连通性

1. 并查集

class UnionFind {
  private:
    vector<int> _parent;
    int _count;
  public:
    UnionFind(int n): _count(n), _parent(n) {
        for (int i = 0; i < n; i++) {
            _parent[i] = i;
        }
    }
    int find(int x) {
        return _parent[x] == x ? x: _parent[x] = find(_parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        _parent[y] = x;
        _count--;
        return true;
    }
    int count() const {
        return _count;
    }
};

拓扑排序

vector<int> topologySort(int n, vector<vector<int>>& edges) {
    vector<int> order, deg(n);
    vector<vector<int>> G(n);
    for (auto& e: edges) {
        G[e[0]].push_back(e[1]);
        deg[e[1]]--;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) {
            q.push(i);
            order.push_back(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            deg[v]--;
            if (deg[v] == 0) {
                order.push_back(v);
                q.push(v);
            }
        }
    }

    return order;
}

图算法题

2065. 最大化一张图中的路径价值

1. 问题理解

   给定无向图、点和边的权值，求包含0节点的环中，满足边权不超过maxTime的点权最大值。

2. 建模和解决

   建有向图，回溯法遍历所有节点。

3. 代码

   时间复杂度：O(N+M)，M是边数，N是节点数。 空间复杂度：O(N+M)

class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<PII>> G(n);
        for (auto& e: edges) {
            G[e[0]].emplace_back(e[1], e[2]);
            G[e[1]].emplace_back(e[0], e[2]);
        }
        vector<int> seen(n);
        seen[0] = true;
        int ans = 0;
        function<void(int, int, int)> dfs = [&](int u, int time, int value) {
            if (u == 0) {
                ans = max(ans, value);
            }
            for (auto& [v, dist]: G[u]) {
                if (time + dist <= maxTime) {
                    if (!seen[v]) {
                        seen[v] = true;
                        dfs(v, time + dist, value + values[v]);
                        seen[v] = false;
                    } else {
                        dfs(v, time + dist, value);
                    }
                }
            }
        };

        dfs(0, 0, values[0]);

        return ans;
    }
};

1632. 矩阵转换后的秩

1. 问题理解

   秩定义了坐标（i，j）间的依赖关系，计算矩阵的秩。

2. 建模和解决

   1. 以坐标（i，j）=> i*m+i为节点建有向图，边为秩定义建立。
   2. 同一行和同一列中相同value的节点（利用并查集）属于同一个连通分量，排序后建立值小节点连通分量到值大节点的分量的边。
   3. 拓扑排序时，初始秩为1，存在 u->v的边，则R(v) = max(R[v], R[u]+1)，类似于2050. 并行课程 III

3. 代码

   时间复杂度：O(NMlog(max(NM)))，N、M为矩阵行列。

using PII = pair<int, int>;

class UnionFind {
  private:
    vector<int> _parent;
    int _count;
  public:
    UnionFind(int n): _count(n), _parent(n) {
        for (int i = 0; i < n; i++) {
            _parent[i] = i;
        }
    }
    int find(int x) {
        return _parent[x] == x ? x: _parent[x] = find(_parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        _parent[y] = x;
        _count--;
        return true;
    }
    int count() const {
        return _count;
    }
};

class Solution {
  public:
    vector<vector<int>> matrixRankTransform(vector<vector<int>> &mat) {
        int n = mat.size(), m = mat[0].size();
        UnionFind uf(n*m);
		
		// row range
        for (int i = 0; i < n; i++) {
            unordered_map<int, vector<int>> mm; // value => [i*m+j];
            for (int j = 0; j < m; j++) {
                mm[mat[i][j]].push_back(i*m+j);
            }
            for (auto& [val, idxs]: mm) {
                for (int k = 1; k < idxs.size(); k++) {
                    uf.unite(idxs[k - 1], idxs[k]);
                }
            }
        }
		
		// column range
        for (int j = 0; j < m; j++) {
            unordered_map<int, vector<int>> mm; // value => [i*m+j];
            for (int i = 0; i < n; i++) {
                mm[mat[i][j]].push_back(i*m+j);
            }
            for (auto &[val, idxs] : mm) {
                for (int k = 1; k < idxs.size(); k++) {
                    uf.unite(idxs[k - 1], idxs[k]);
                }
            }
        }

        // build graph
        vector<vector<int>> G(n*m);
        vector<int> deg(n*m);
        for (int i = 0; i < n; i++) {
            vector<PII> nums; // value => index
            for (int j = 0; j < m; j++) {
                nums.emplace_back(mat[i][j], i*m+j);
            }
            sort(nums.begin(), nums.end());
            for (int k = 1; k < nums.size(); k++) {
                if (nums[k-1].first < nums[k].first) {
                    int u = uf.find(nums[k - 1].second);
                    int v = uf.find(nums[k].second);
					// build edge by order
                    G[u].push_back(v);
                    deg[v]++;
                }
            }
        }
        for (int j = 0; j < m; j++) {
            vector<PII> nums; // value => index
            for (int i = 0; i < n; i++) {
                nums.emplace_back(mat[i][j], i * m + j);
            }
            sort(nums.begin(), nums.end());
            for (int k = 1; k < nums.size(); k++) {
                if (nums[k - 1].first < nums[k].first) {
                    int u = uf.find(nums[k - 1].second);
                    int v = uf.find(nums[k].second);
                    G[u].push_back(v);
                    deg[v]++;
                }
            }
        }
		
		// topology sort
        queue<int> q;
        for (int i = 0; i < n * m; i++) {
            if (deg[i] == 0 && uf.find(i) == i) {
                q.push(i);
            }
        }

        vector<int> r(n*m, 1);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v: G[u]) {
				// dp
                r[v] = max(r[v], r[u]+1);
                deg[v]--;
                if (deg[v] == 0) {
                    q.push(v);
                }
            }
        }

        vector<vector<int>> res(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = r[uf.find(i*m+j)];
            }
        }

        return res;
    }
};

2203. 得到要求路径的最小带权子图

1. 问题理解

   带权有向图，求解从src1，src2到dst路径组成的最小子图。

2. 建模和解决

   1. 最短路问题，分别以src1、src2和dst计算单源最短路。
   2. 以某一个节点为中继，枚举最小子图。

3. 代码

   时间复杂度：O(N+Mlog(M))，N、M分别为节点和边数。 空间复杂度：O(NM)

using PII = pair<int, int>;
class Solution {
  public:
    vector<long> dijkstra(vector<vector<PII>>& G, int s) {
        vector<long> dist(G.size(), LONG_MAX/3);
        dist[s] = 0;
        priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
        pq.emplace(0, s);

        while (!pq.empty()) {
            auto [du, u] = pq.top();
            pq.pop();
            if (du > dist[u]) continue;
            for (auto& [v, dv]: G[u]) {
                long d = dist[u] + dv;
                if (dist[v] > d) {
                    dist[v] = d;
                    pq.emplace(d, v);
                }
            }
        }

        return dist;
    }

    long long minimumWeight(int n, vector<vector<int>> &edges, int src1, int src2, int dest) {
        vector<vector<PII>> G(n), RG(n);
        for (auto& e: edges) {
            int u = e[0], v = e[1], d = e[2];
            G[u].emplace_back(v, d);
            RG[v].emplace_back(u, d);
        }

        auto da = dijkstra(G, src1);
        auto db = dijkstra(G, src2);
        auto dc = dijkstra(RG, dest);

        long res = LONG_MAX/3;
        for (int i = 0; i < n; i++) {
            res = min(res, da[i]+db[i]+dc[i]);
        }

        return res < LONG_MAX/3 ? res: -1;
    }
};

1489. 找到最小生成树里的关键边和伪关键边

1. 问题理解

   带权无向图中求关键边（去除边最小生成树权重增大）和伪关键边（去除边不影响最小生成树）。

2. 建模和解决

   1. 计算最小生成树，记录最小边权。
   2. 枚举每条边，判断关键和伪关键边性质。

3. 代码

   时间复杂度：O(M^2\alpha(N))，N、M分别为节点和边数。 空间复杂度：O(N+M)

using VII = vector<vector<int>>;

class UnionFind {
  private:
    vector<int> _parent;
    int _count;
  public:
    UnionFind(int n): _count(n), _parent(n) {
        for (int i = 0; i < n; i++) {
            _parent[i] = i;
        }
    }
    int find(int x) {
        return _parent[x] == x ? x: _parent[x] = find(_parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        _parent[y] = x;
        _count--;
        return true;
    }
    int count() const {
        return _count;
    }
};

class Solution {
  public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> &edges) {
        int m = edges.size();
        for (int i = 0; i < m; i++) {
            edges[i].push_back(i);
        }
        int minValue = 0;
        sort(edges.begin(), edges.end(), [](auto& x, auto& y) {
            return x[2] < y[2];
        });
        UnionFind fa(n);
        for (auto& e: edges) {
            if (fa.unite(e[0], e[1])) {
                minValue += e[2];
            }
        }

        vector<vector<int>> res(2);
        for (int i = 0; i < m; i++) {
            int value = 0;
            UnionFind fb(n);
            for (int k = 0; k < m; k++) {
                if (i != k && fb.unite(edges[k][0], edges[k][1])) {
                    value += edges[k][2];
                }
            }
            if (fb.count() != 1 || (fb.count() == 1 && value > minValue)) {
                res[0].push_back(edges[i][3]);
                continue;
            }

            UnionFind fc(n);
            fc.unite(edges[i][0], edges[i][1]);
            value = edges[i][2];
            for (int k = 0; k < m; k++) {
                if (i != k && fc.unite(edges[k][0], edges[k][1])) {
                    value += edges[k][2];
                }
            }
            if (value == minValue) {
                res[1].push_back(edges[i][3]);
            }
        }

        return res;
    }
};

2050. 并行课程 III

1. 问题理解

   课程相互依赖，并且修完耗费一定时间，求解修完所有课的最短时间。

2. 建模和解决

   1. 典型的拓扑排序问题。
   2. 动态规划解决课程开始的最短时间，存在u->v边，则start[v] = max(start[v], start[u] + time[v])。

3. 代码

   时间复杂度：O(N+M)，N、M分别为节点和边数。 空间复杂度：O(N+M)

class Solution {
public:
  int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
      vector<int> start(n), deg(n);
      VII G(n);
      for (auto& e: relations) {
          G[e[0]-1].push_back(e[1]-1);
          deg[e[1]-1]++;
      }
      queue<int> q;
      for (int i = 0; i < n; i++) {
          if (deg[i] == 0) {
              q.push(i);
          }
      }
      int ans = 0;
      while (!q.empty()) {
          int u = q.front();
          q.pop();
          ans = max(ans, start[u]+time[u]);
          for (int v: G[u]) {
              deg[v]--;
              start[v] = max(start[v], start[u] + time[u]);
              if (deg[v] == 0) {
                  q.push(v);
              }
          }
      }

      return ans;
  }
};

1928. 规定时间内到达终点的最小花费

1. 问题理解

   点和边都带权的无向图，求救从0出发到n-1，且边权不大于maxTime的最小点权值。

2. 建模和解决

   回溯+剪枝。

3. 代码

using MII = unordered_map<int, int>;

class Solution {
private:
    int _cost = 0;
    int _costTime = 0;
    int _minCost = INT_MAX;
    int _maxTime, _n;
    vector<MII> _G;
    vector<int> _fees;
    vector<bool> _seen;
    vector<int> _minPathTime, _minPathCost;
public:
    int minCost(int maxTime, vector<vector<int>> &edges, vector<int> &fees) {
        _n = fees.size();
        _G.resize(_n);
        _fees = fees;
        _seen.resize(_n);
        _minPathCost = vector<int>(_n, INT_MAX);
        _minPathTime = vector<int>(_n, INT_MAX);
        for (auto& e: edges) {
            if (_G[e[1]].count(e[0])) {
                _G[e[1]][e[0]] = min(_G[e[1]][e[0]], e[2]);
                _G[e[0]][e[1]] = min(_G[e[0]][e[1]], e[2]);
            } else {
                _G[e[0]][e[1]] = _G[e[1]][e[0]] = e[2];
            }
        }
        _maxTime = maxTime;
        backtrack(0);
        return _minCost == INT_MAX ? -1: _minCost;

    }

    void backtrack(int u) {
		// 剪枝很关键
        if (_costTime > _maxTime || _cost > _minCost || (_cost > _minPathCost[u] && _costTime > _minPathTime[u])) {
            return;;
        }
        if (u == _n-1) {
            _minCost = min(_minCost, _cost+_fees[u]);
            return;
        }

        _seen[u] = true;
        _cost += _fees[u];
        _minPathCost[u] = min(_minPathCost[u], _cost);
        _minPathTime[u] = min(_minPathTime[u], _costTime);
        for (auto& v: _G[u]) {
            if (!_seen[v.first]) {
                _costTime += v.second;
                backtrack(v.first);
                _costTime -= v.second;
            }
        }
        _seen[u] = false;
        _cost -= _fees[u];
    }
};

2076. 处理含限制条件的好友请求

1. 问题理解

   合并连通分量时满足非连通性约束。

2. 建模和解决

   并查集，每次合并u–v时，检查是否满足yeu’s

3. 代码

   时间复杂度：O(KM\alpha(N))，K、M分别是请求和约束条件数目，N为节点数 空间复杂度：O(N)

class Solution {
  private:
    vector<int> _parent;
  public:
    vector<bool> friendRequests(int n, vector<vector<int>> &res, vector<vector<int>> &req) {
        _parent.resize(n);
        for (int i = 0; i < n; i++) {
            _parent[i] = i;
        }
        vector<bool> ans;
        for (auto& r: req) {
            int x = find(r[0]), y = find(r[1]);
            if (x == y) {
                ans.push_back(true);
            } else {
                bool ok = true;
                for (auto& rs: res) {
                    int u = find(rs[0]), v = find(rs[1]);
                    if ((x == u && y == v) ||(x == v && y == u)) {
                        ok = false;
                        break;
                    }
                }

                if (ok) {
                    unite(x, y);
                    ans.push_back(true);
                } else {
                    ans.push_back(false);
                }
            }
        }

        return ans;
    }
    int find(int x) {
        return _parent[x] == x? x: _parent[x] = find(_parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        _parent[y] = x;
        return true;
    }
};

2246. 相邻字符不同的最长路径

1. 问题理解

   附带条件的树最长直径。

2. 建模和解决

   DFS，回溯时计算最长路径

3. 代码

   时间复杂度：O(N)，N为节点数 空间复杂度：O(N^2)

class Solution {
  public:
    int longestPath(vector<int> &parent, string s) {
        int n = parent.size();
        vector<vector<int>> tree(n);
        for (int i = 1; i < n; i++) {
            tree[parent[i]].push_back(i);
        }
        int ans = 0;

        function<int(int)> dfs = [&](int u) -> int {
            int longest = 0;
            for (int v: tree[u]) {
                int len = dfs(v) + 1;
                if (s[u] != s[v]) {
                    ans = max(ans, longest + len);
                    longest = max(longest, len);
                }
            }

            return longest;
        };
        dfs(0);

        return ans + 1;
    }
};