分享丨【算法题单】图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。原文链接：https://leetcode.cn/circle/discuss/01LUak/

一、图的遍历

§1.1 深度优先搜索（DFS）

找连通块、判断是否有环（如 207 题）等。部分题目做法不止一种。

模板（计算每个连通块的大小）：

def solve(n: int, edges: list[list[int]]) -> list[int]:
    # 节点编号从 0 到 n-1
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)  # 无向图

    vis = [False] * n

    def dfs(x: int) -> int:
        vis[x] = True  # 避免重复访问节点
        size = 1
        for y in g[x]:
            if not vis[y]:
                size += dfs(y)
        return size

    # 计算每个连通块的大小
    ans = []
    for i, b in enumerate(vis):
        if not b:  # i 没有访问过
            size = dfs(i)
            ans.append(size)
    return ans

java

class Solution {
    public List<Integer> solve(int n, int[][] edges) {
        // 节点编号从 0 到 n-1
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x); // 无向图
        }

        // 计算每个连通块的大小
        List<Integer> ans = new ArrayList<>();
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!vis[i]) { // i 没有访问过
                int size = dfs(i, vis, g);
                ans.add(size);
            }
        }
        return ans;
    }

    private int dfs(int x, boolean[] vis, List<Integer>[] g) {
        vis[x] = true; // 避免重复访问节点
        int size = 1;
        for (int y : g[x]) {
            if (!vis[y]) {
                size += dfs(y, vis, g);
            }
        }
        return size;
    }
}

cpp

vector<int> solve(int n, vector<vector<int>>& edges) {
    // 节点编号从 0 到 n-1
    vector<vector<int>> g(n);
    for (auto& e : edges) {
        int x = e[0], y = e[1];
        g[x].push_back(y);
        g[y].push_back(x); // 无向图
    }

    vector<int8_t> vis(n);

    // lambda 递归
    auto dfs = [&](this auto&& dfs, int x) -> int {
        vis[x] = true; // 避免重复访问节点
        int size = 1;
        for (int y : g[x]) {
            if (!vis[y]) {
                size += dfs(y);
            }
        }
        return size;
    };

    // 计算每个连通块的大小
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) { // i 没有访问过
            int size = dfs(i);
            ans.push_back(size);
        }
    }
    return ans;
}

func solve(n int, edges [][]int) (ans []int) {
	// 节点编号从 0 到 n-1
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x) // 无向图
	}

	vis := make([]bool, n)

	var dfs func(int) int
	dfs = func(x int) int {
		vis[x] = true // 避免重复访问节点
		size := 1
		for _, y := range g[x] {
			if !vis[y] {
				size += dfs(y)
			}
		}
		return size
	}

	// 计算每个连通块的大小
	for i, b := range vis {
		if !b { // i 没有访问过
			size := dfs(i)
			ans = append(ans, size)
		}
	}
	return
}

思维扩展：

1298. 你能从盒子里获得的最大糖果数 1825

§1.2 广度优先搜索（BFS）

求最短路等。要求边权都是 $1$ （或者说都是同一个正数）。

模板（单源最短路）：

# 计算从 start 到各个节点的最短路长度
# 如果节点不可达，则最短路长度为 -1
# 节点编号从 0 到 n-1，边权均为 1
def bfs(n: int, edges: list[list[int]], start: int) -> list[int]:
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)  # 无向图

    dis = [-1] * n  # -1 表示尚未访问到
    dis[start] = 0
    q = deque([start])
    while q:
        x = q.popleft()
        for y in g[x]:
            if dis[y] < 0:
                dis[y] = dis[x] + 1
                q.append(y)
    return dis

java

class Solution {
    // 计算从 start 到各个节点的最短路长度
    // 如果节点不可达，则最短路长度为 -1
    // 节点编号从 0 到 n-1，边权均为 1
    public int[] bfs(int n, int[][] edges, int start) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 无向图
        }

        int[] dis = new int[n];
        Arrays.fill(dis, -1); // -1 表示尚未访问到
        Queue<Integer> q = new ArrayDeque<>();
        dis[start] = 0;
        q.offer(start);
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y : g[x]) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + 1;
                    q.offer(y);
                }
            }
        }
        return dis;
    }
}

cpp

// 计算从 start 到各个节点的最短路长度
// 如果节点不可达，则最短路长度为 -1
// 节点编号从 0 到 n-1，边权均为 1
vector<int> bfs(int n, vector<vector<int>>& edges, int start) {
    vector<vector<int>> g(n);
    for (auto& e : edges) {
        int x = e[0], y = e[1];
        g[x].push_back(y);
        g[y].push_back(x); // 无向图
    }

    vector<int> dis(n, -1); // -1 表示尚未访问到
    queue<int> q;
    dis[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x]) {
            if (dis[y] < 0) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    return dis;
}

// 计算从 start 到各个节点的最短路长度
// 如果节点不可达，则最短路长度为 -1
// 节点编号从 0 到 n-1，边权均为 1
func bfs(n int, edges [][]int, start int) []int {
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x) // 无向图
	}

	dis := make([]int, n)
	for i := range dis {
		dis[i] = -1 // -1 表示尚未访问到
	}
	dis[start] = 0
	q := []int{start}
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			if dis[y] < 0 {
				dis[y] = dis[x] + 1
				q = append(q, y)
			}
		}
	}
	return dis
}

§1.3 图论建模 + BFS 最短路

把状态抽象成图上的点，用 BFS 遍历这张图，计算从初始状态到目标状态的最短路长度。

可以锻炼状态设计能力。

专题：跳跃游戏

注：关于网格图的 DFS 和 BFS，请看网格图题单。

二、拓扑排序

图论题单图论算法图论题目 LeetCode 力扣图论灵茶山艾府灵神灵神题单

把拓扑排序想象成一个黑盒，给它一堆杂乱的先修课约束，它会给你一个井井有条的课程学习安排。

这一种在图上的「排序」，可以把杂乱的点排成一排。前提条件是图中无环，从而保证每条边都是从排在前面的点，指向排在后面的点。即对于任意有向边 $x \to y$ ， $x$ 一定在 $y$ 之前。

§2.1 拓扑排序

模板：

# 返回有向无环图（DAG）的其中一个拓扑序
# 如果图中有环，返回空列表
# 节点编号从 0 到 n-1
def topologicalSort(n: int, edges: list[list[int]]) -> list[int]:
    g = [[] for _ in range(n)]
    in_deg = [0] * n
    for x, y in edges:
        g[x].append(y)
        in_deg[y] += 1  # 统计 y 的先修课数量

    topo_order = []
    q = deque(i for i, d in enumerate(in_deg) if d == 0)  # 没有先修课，可以直接上
    while q:
        x = q.popleft()
        topo_order.append(x)
        for y in g[x]:
            in_deg[y] -= 1  # 修完 x 后，y 的先修课数量减一
            if in_deg[y] == 0:  # y 的先修课全部上完
                q.append(y)  # 加入学习队列

    if len(topo_order) < n:  # 图中有环
        return []
    return topo_order

java

class Solution {
    // 返回有向无环图（DAG）的其中一个拓扑序
    // 如果图中有环，返回空列表
    // 节点编号从 0 到 n-1
    public List<Integer> topologicalSort(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        int[] inDeg = new int[n];
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            inDeg[y]++; // 统计 y 的先修课数量
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) { // 没有先修课，可以直接上
                q.offer(i); // 加入学习队列
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!q.isEmpty()) {
            int x = q.poll();
            topoOrder.add(x);
            for (int y : g[x]) {
                inDeg[y]--; // 修完 x 后，y 的先修课数量减一
                if (inDeg[y] == 0) { // y 的先修课全部上完
                    q.offer(y); // 加入学习队列
                }
            }
        }

        if (topoOrder.size() < n) { // 图中有环
            return List.of();
        }
        return topoOrder;
    }
}

cpp

// 返回有向无环图（DAG）的其中一个拓扑序
// 如果图中有环，返回空列表
// 节点编号从 0 到 n-1
vector<int> topologicalSort(int n, vector<vector<int>>& edges) {
    vector<vector<int>> g(n);
    vector<int> in_deg(n);
    for (auto& e : edges) {
        int x = e[0], y = e[1];
        g[x].push_back(y);
        in_deg[y]++; // 统计 y 的先修课数量
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (in_deg[i] == 0) { // 没有先修课，可以直接上
            q.push(i); // 加入学习队列
        }
    }

    vector<int> topo_order;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        topo_order.push_back(x);
        for (int y : g[x]) {
            in_deg[y]--; // 修完 x 后，y 的先修课数量减一
            if (in_deg[y] == 0) { // y 的先修课全部上完
                q.push(y); // 加入学习队列
            }
        }
    }

    if (topo_order.size() < n) { // 图中有环
        return {};
    }
    return topo_order;
}

// 返回有向无环图（DAG）的其中一个拓扑序
// 如果图中有环，返回 nil
// 节点编号从 0 到 n-1
func topologicalSort(n int, edges [][]int) []int {
	g := make([][]int, n)
	inDeg := make([]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		inDeg[y]++ // 统计 y 的先修课数量
	}

	q := make([]int, 0, n)
	topoOrder := q
	for i, d := range inDeg {
		if d == 0 { // 没有先修课，可以直接上
			q = append(q, i) // 加入学习队列
		}
	}
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			inDeg[y]-- // 修完 x 后， y 的先修课数量减一
			if inDeg[y] == 0 { // y 的先修课全部上完
				q = append(q, y) // 加入学习队列
			}
		}
	}

	if cap(q) > 0 { // 图中有环
		return nil
	}
	return topoOrder[:n]
}

学习拓扑排序前，请先完成 1557. 可以到达所有点的最少点数目，有助于理解拓扑排序。

思维扩展：

§2.2 在拓扑序上 DP

一般是刷表法。

§2.3 基环树

基环树介绍

思维扩展：

287. 寻找重复数

三、最短路

§3.1 单源最短路：Dijkstra 算法

Dijkstra 算法介绍

模板：

# 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = math.inf
# 要求：没有负数边权
# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度。注意堆中有 O(m) 个元素
def shortestPathDijkstra(n: int, edges: list[list[int]], start: int) -> list[int]:
    # 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
    g = [[] for _ in range(n)]  # 邻接表
    for x, y, wt in edges:
        g[x].append((y, wt))
        # g[y].append((x, wt))  # 无向图加上这行

    dis = [math.inf] * n
    dis[start] = 0  # 起点到自己的距离是 0
    h = [(0, start)]  # 堆中保存 (起点到节点 x 的最短路长度，节点 x)

    while h:
        dis_x, x = heappop(h)
        if dis_x > dis[x]:  # x 之前出堆过
            continue
        for y, wt in g[x]:
            new_dis_y = dis_x + wt
            if new_dis_y < dis[y]:
                dis[y] = new_dis_y  # 更新 x 的邻居的最短路
                # 懒更新堆：只插入数据，不更新堆中数据
                # 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
                heappush(h, (new_dis_y, y))

    return dis

java

class Solution {
    // 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = Integer.MAX_VALUE
    // 要求：没有负数边权
    // 时间复杂度 O(n + mlogm)，注意堆中有 O(m) 个元素
    private int[] shortestPathDijkstra(int n, int[][] edges, int start) {
        // 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
        List<int[]>[] g = new ArrayList[n]; // 邻接表
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int wt = e[2];
            g[x].add(new int[]{y, wt});
            // g[y].add(new int[]{x, wt}); // 无向图加上这行
        }

        int[] dis = new int[n]; // **如果数据范围大，改成 long[]**
        Arrays.fill(dis, Integer.MAX_VALUE);
        // 堆中保存 (起点到节点 x 的最短路长度，节点 x)
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        dis[start] = 0; // 起点到自己的距离是 0
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int disX = top[0];
            int x = top[1];
            if (disX > dis[x]) { // x 之前出堆过
                continue;
            }
            for (int[] e : g[x]) {
                int y = e[0];
                int wt = e[1];
                int newDisY = disX + wt;
                if (newDisY < dis[y]) {
                    dis[y] = newDisY; // 更新 x 的邻居的最短路
                    // 懒更新堆：只插入数据，不更新堆中数据
                    // 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
                    pq.offer(new int[]{newDisY, y});
                }
            }
        }

        return dis;
    }
}

cpp

// 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = LLONG_MAX
// 要求：没有负数边权
// 时间复杂度 O(n + mlogm)，注意堆中有 O(m) 个元素
vector<long long> shortestPathDijkstra(int n, vector<vector<int>>& edges, int start) {
    // 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
    vector<vector<pair<int, int>>> g(n); // 邻接表
    for (auto& e : edges) {
        int x = e[0], y = e[1], wt = e[2];
        g[x].emplace_back(y, wt);
        // g[y].emplace_back(x, wt); // 无向图加上这行
    }

    vector<long long> dis(n, LLONG_MAX);
    // 堆中保存 (起点到节点 x 的最短路长度，节点 x)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dis[start] = 0; // 起点到自己的距离是 0
    pq.emplace(0, start);

    while (!pq.empty()) {
        auto [dis_x, x] = pq.top();
        pq.pop();
        if (dis_x > dis[x]) { // x 之前出堆过
            continue;
        }
        for (auto& [y, wt] : g[x]) {
            auto new_dis_y = dis_x + wt;
            if (new_dis_y < dis[y]) {
                dis[y] = new_dis_y; // 更新 x 的邻居的最短路
                // 懒更新堆：只插入数据，不更新堆中数据
                // 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
                pq.emplace(new_dis_y, y);
            }
        }
    }

    return dis;
}

// 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = math.MaxInt
// 要求：没有负数边权
// 时间复杂度 O(n + mlogm)，注意堆中有 O(m) 个元素
func shortestPathDijkstra(n int, edges [][]int, start int) []int {
    // 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
    type edge struct{ to, wt int }
    g := make([][]edge, n) // 邻接表
    for _, e := range edges {
        x, y, wt := e[0], e[1], e[2]
        g[x] = append(g[x], edge{y, wt})
        // g[y] = append(g[y], edge{x, wt}) // 无向图加上这行
    }

    dis := make([]int, n)
    for i := range dis {
        dis[i] = math.MaxInt
    }
    dis[start] = 0 // 起点到自己的距离是 0
    // 堆中保存 (起点到节点 x 的最短路长度，节点 x)
    h := &hp{{0, start}}

    for h.Len() > 0 {
        p := heap.Pop(h).(pair)
        disX, x := p.dis, p.x
        if disX > dis[x] { // x 之前出堆过
            continue
        }
        for _, e := range g[x] {
            y := e.to
            newDisY := disX + e.wt
            if newDisY < dis[y] {
                dis[y] = newDisY // 更新 x 的邻居的最短路
                // 懒更新堆：只插入数据，不更新堆中数据
                // 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
                heap.Push(h, pair{newDisY, y})
            }
        }
    }

    return dis
}

type pair struct{ dis, x int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

分层图最短路：

SPFA 与差分约束：

力扣上的 SPFA 题很少。

2589. 完成所有任务的最少时间 2381 做法不止一种

§3.2 全源最短路：Floyd 算法

Floyd 算法本质是三维 DP。理解 DP 一定要基于空间优化前的写法。

带你发明 Floyd 算法：从记忆化搜索到递推

模板：

# 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
# 如果无法从 i 到 j，则最短路长度为 math.inf
# 允许负数边权
# 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
# 节点编号从 0 到 n-1
# 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
def shortestPathFloyd(self, n: int, edges: list[list[int]]) -> list[list[int]]:
    f = [[math.inf] * n for _ in range(n)]
    for i in range(n):
        f[i][i] = 0

    for x, y, wt in edges:
        f[x][y] = min(f[x][y], wt)  # 如果有重边，取边权最小值
        f[y][x] = min(f[y][x], wt)  # 无向图

    for k in range(n):
        for i in range(n):
            if f[i][k] == math.inf:  # 针对稀疏图的优化
                continue
            for j in range(n):
                f[i][j] = min(f[i][j], f[i][k] + f[k][j])
    return f

java

class Solution {
    // 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
    // 如果无法从 i 到 j，则最短路长度为 Long.MAX_VALUE / 2
    // 允许负数边权
    // 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
    // 节点编号从 0 到 n-1
    // 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
    public long[][] shortestPathFloyd(int n, int[][] edges) {
        final long INF = Long.MAX_VALUE / 2; // 防止加法溢出
        long[][] f = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], INF);
            f[i][i] = 0;
        }

        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int wt = e[2];
            f[x][y] = Math.min(f[x][y], wt); // 如果有重边，取边权最小值
            f[y][x] = Math.min(f[y][x], wt); // 无向图
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (f[i][k] == INF) { // 针对稀疏图的优化
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        return f;
    }
}

cpp

// 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
// 如果无法从 i 到 j，则最短路长度为 LLONG_MAX / 2
// 允许负数边权
// 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
// 节点编号从 0 到 n-1
// 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
vector<vector<long long>> shortestPathFloyd(int n, vector<vector<int>>& edges) {
    const long long INF = LLONG_MAX / 2; // 防止加法溢出
    vector f(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) {
        f[i][i] = 0;
    }

    for (auto& e : edges) {
        int x = e[0], y = e[1];
        long long wt = e[2];
        f[x][y] = min(f[x][y], wt); // 如果有重边，取边权最小值
        f[y][x] = min(f[y][x], wt); // 无向图
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (f[i][k] == INF) { // 针对稀疏图的优化
                continue;
            }
            for (int j = 0; j < n; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    return f;
}

// 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
// 如果无法从 i 到 j，则最短路长度为 math.MaxInt / 2
// 允许负数边权
// 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
// 节点编号从 0 到 n-1
// 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
func shortestPathFloyd(n int, edges [][]int) [][]int {
	const inf = math.MaxInt / 2 // 防止加法溢出
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = inf
		}
		f[i][i] = 0
	}

	for _, e := range edges {
		x, y, wt := e[0], e[1], e[2]
		f[x][y] = min(f[x][y], wt) // 如果有重边，取边权最小值
		f[y][x] = min(f[y][x], wt) // 无向图
	}

	for k := range n {
		for i := range n {
			if f[i][k] == inf { // 针对稀疏图的优化
				continue
			}
			for j := range n {
				f[i][j] = min(f[i][j], f[i][k]+f[k][j])
			}
		}
	}
	return f
}

Bitset 优化 Floyd

四、最小生成树

涉及到 Kruskal 算法和 Prim 算法。前者一般用于稀疏图，后者一般用于稠密图。

注：如果要求最大生成树，把边权从大到小排序。

Kruskal 算法模板（用到了并查集，完整模板见数据结构题单）：

class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己
        self._fa = list(range(n))  # 代表元
        self.cc = n  # 连通块个数

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        # 如果 fa[x] == x，则表示 x 是代表元
        if self._fa[x] != x:
            self._fa[x] = self.find(self._fa[x])  # fa 改成代表元
        return self._fa[x]

    # 把 from 所在集合合并到 to 所在集合中
    # 返回是否合并成功
    def merge(self, from_: int, to: int) -> bool:
        x, y = self.find(from_), self.find(to)
        if x == y:  # from 和 to 在同一个集合，不做合并
            return False
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        self.cc -= 1  # 成功合并，连通块个数减一
        return True


# 计算图的最小生成树的边权之和
# 如果图不连通，返回 math.inf
# 节点编号从 0 到 n-1
# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度
def mstKruskal(n: int, edges: list[list[int]]) -> int:
    edges.sort(key=lambda e: e[2])

    uf = UnionFind(n)
    sum_wt = 0
    for x, y, wt in edges:
        if uf.merge(x, y):
            sum_wt += wt

    if uf.cc > 1:  # 图不连通
        return math.inf
    return sum_wt

java

class UnionFind {
    private final int[] fa; // 代表元
    public int cc; // 连通块个数

    UnionFind(int n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
        cc = n;
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    public int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 把 from 所在集合合并到 to 所在集合中
    // 返回是否合并成功
    public boolean merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return false;
        }
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        cc--; // 成功合并，连通块个数减一
        return true;
    }
}

class Solution {
    // 计算图的最小生成树的边权之和
    // 如果图不连通，返回 Long.MAX_VALUE
    // 节点编号从 0 到 n-1
    // 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度
    public long mstKruskal(int n, int[][] edges) {
        Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));

        UnionFind uf = new UnionFind(n);
        long sumWt = 0;
        for (int[] e : edges) {
            int x = e[0], y = e[1], wt = e[2];
            if (uf.merge(x, y)) {
                sumWt += wt;
            }
        }

        if (uf.cc > 1) { // 图不连通
            return Long.MAX_VALUE;
        }
        return sumWt;
    }
}

cpp

class UnionFind {
    vector<int> fa; // 代表元

public:
    int cc; // 连通块个数

    UnionFind(int n) : fa(n), cc(n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        ranges::iota(fa, 0);
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 把 from 所在集合合并到 to 所在集合中
    // 返回是否合并成功
    bool merge(int from, int to) {
        int x = find(from), y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return false;
        }
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        cc--; // 成功合并，连通块个数减一
        return true;
    }
};

// 计算图的最小生成树的边权之和
// 如果图不连通，返回 LLONG_MAX
// 节点编号从 0 到 n-1
// 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度
long long mstKruskal(int n, vector<vector<int>>& edges) {
    ranges::sort(edges, {}, [](const auto& e) { return e[2]; });

    UnionFind uf(n);
    long long sum_wt = 0;
    for (auto& e : edges) {
        int x = e[0], y = e[1], wt = e[2];
        if (uf.merge(x, y)) {
            sum_wt += wt;
        }
    }

    if (uf.cc > 1) { // 图不连通
        return LLONG_MAX;
    }
    return sum_wt;
}

type unionFind struct {
	fa []int // 代表元
	cc int   // 连通块个数
}

func newUnionFind(n int) unionFind {
	fa := make([]int, n)
	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
	// 集合 i 的代表元是自己
	for i := range fa {
		fa[i] = i
	}
	return unionFind{fa, n}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
	// 如果 fa[x] == x，则表示 x 是代表元
	if u.fa[x] != x {
		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
	}
	return u.fa[x]
}

// 把 from 所在集合合并到 to 所在集合中
// 返回是否合并成功
func (u *unionFind) merge(from, to int) bool {
	x, y := u.find(from), u.find(to)
	if x == y { // from 和 to 在同一个集合，不做合并
		return false
	}
	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
	u.cc--      // 成功合并，连通块个数减一
	return true
}

// 计算图的最小生成树的边权之和
// 如果图不连通，返回 math.MaxInt
// 节点编号从 0 到 n-1
// 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度
func mstKruskal(n int, edges [][]int) int {
	slices.SortFunc(edges, func(a, b []int) int { return a[2] - b[2] })

	uf := newUnionFind(n)
	sumWt := 0
	for _, e := range edges {
		x, y, wt := e[0], e[1], e[2]
		if uf.merge(x, y) {
			sumWt += wt
		}
	}

	if uf.cc > 1 { // 图不连通
		return math.MaxInt
	}
	return sumWt
}

思维扩展

3219. 切蛋糕的最小总开销 II

五、欧拉路径/欧拉回路

涉及到 Hierholzer 算法。

六、强连通分量/双连通分量

涉及到 Tarjan 算法。

七、二分图染色

模板（交替染色法）：

# 返回图的二染色
# 如果是二分图，返回每个节点的颜色，用 1 和 2 表示两种颜色
# 如果不是二分图，返回空列表
# 时间复杂度 O(n+m)，n 是点数，m 是边数
def colorBipartite(n: int, edges: list[list[int]]) -> list[int]:
    # 建图（节点编号从 0 到 n-1）
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)

    # colors[i] = 0 表示未访问节点 i
    # colors[i] = 1 表示节点 i 为红色
    # colors[i] = 2 表示节点 i 为蓝色
    colors = [0] * n

    def dfs(x: int, c: int) -> bool:
        colors[x] = c  # 节点 x 染成颜色 c
        for y in g[x]:
            # 邻居 y 的颜色与 x 的相同，说明不是二分图，返回 False
            # 或者继续递归，发现不是二分图，返回 False
            if colors[y] == c or \
               colors[y] == 0 and not dfs(y, 3 - c):  # 1 和 2 交替染色
                return False
        return True

    # 可能有多个连通块
    for i, c in enumerate(colors):
        if c == 0 and not dfs(i, 1):
            # 从节点 i 开始递归，发现 i 所在连通块不是二分图
            return []
    return colors

java

class Solution {
    // 返回图的二染色
    // 如果是二分图，返回每个节点的颜色，用 1 和 2 表示两种颜色
    // 如果不是二分图，返回空列表
    // 时间复杂度 O(n+m)，n 是点数，m 是边数
    private int[] colorBipartite(int n, int[][] edges) {
        // 建图（节点编号从 0 到 n-1）
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        // colors[i] = 0 表示未访问节点 i
        // colors[i] = 1 表示节点 i 为红色
        // colors[i] = 2 表示节点 i 为蓝色
        int[] colors = new int[n];

        for (int i = 0; i < n; i++) {
            if (colors[i] == 0 && !dfs(i, 1, g, colors)) {
                // 从节点 i 开始递归，发现 i 所在连通块不是二分图
                return new int[]{};
            }
        }
        return colors;
    }

    private boolean dfs(int x, int c, List<Integer>[] g, int[] colors) {
        colors[x] = c; // 节点 x 染成颜色 c
        for (int y : g[x]) {
            // 邻居 y 的颜色与 x 的相同，说明不是二分图，返回 false
            // 或者继续递归，发现不是二分图，返回 false
            if (colors[y] == c || 
                colors[y] == 0 && !dfs(y, 3 - c, g, colors)) { // 1 和 2 交替染色
                return false;
            }
        }
        return true;
    }
}

cpp

// 返回图的二染色
// 如果是二分图，返回每个节点的颜色，用 1 和 2 表示两种颜色
// 如果不是二分图，返回空列表
// 时间复杂度 O(n+m)，n 是点数，m 是边数
vector<int8_t> colorBipartite(int n, vector<vector<int>>& edges) {
    // 建图（节点编号从 0 到 n-1）
    vector<vector<int>> g(n);
    for (auto& e : edges) {
        int x = e[0], y = e[1];
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // colors[i] = 0 表示未访问节点 i
    // colors[i] = 1 表示节点 i 为红色
    // colors[i] = 2 表示节点 i 为蓝色
    vector<int8_t> colors(n);

    // lambda 递归
    auto dfs = [&](this auto&& dfs, int x, int8_t c) -> bool {
        colors[x] = c; // 节点 x 染成颜色 c
        for (int y : g[x]) {
            // 邻居 y 的颜色与 x 的相同，说明不是二分图，返回 false
            // 或者继续递归，发现不是二分图，返回 false
            if (colors[y] == c || 
                colors[y] == 0 && !dfs(y, 3 - c)) { // 1 和 2 交替染色
                return false;
            }
        }
        return true;
    };

    // 可能有多个连通块
    for (int i = 0; i < n; i++) {
        if (colors[i] == 0 && !dfs(i, 1)) {
            // 从节点 i 开始递归，发现 i 所在连通块不是二分图
            return {};
        }
    }
    return colors;
}

// 返回图的二染色
// 如果是二分图，返回每个节点的颜色，用 1 和 2 表示两种颜色
// 如果不是二分图，返回空列表
// 时间复杂度 O(n+m)，n 是点数，m 是边数
func colorBipartite(n int, edges [][]int) []int8 {
    // 建图（节点编号从 0 到 n-1）
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

    // colors[i] = 0 表示未访问节点 i
    // colors[i] = 1 表示节点 i 为红色
    // colors[i] = 2 表示节点 i 为蓝色
    colors := make([]int8, n)

    var dfs func(int, int8) bool
    dfs = func(x int, c int8) bool {
        colors[x] = c // 节点 x 染成颜色 c
        for _, y := range g[x] {
            // 邻居 y 的颜色与 x 的相同，说明不是二分图，返回 false
            // 或者继续递归，发现不是二分图，返回 false
            if colors[y] == c ||
                colors[y] == 0 && !dfs(y, 3-c) { // 1 和 2 交替染色
                return false
            }
        }
        return true
    }

    // 可能有多个连通块
    for i, c := range colors {
        if c == 0 && !dfs(i, 1) {
            // 从节点 i 开始递归，发现 i 所在连通块不是二分图
            return nil
        }
    }
    return colors
}

关于二分图的最大匹配，见下面网络流的题目。其中标有「一对一」的题目也可以用带权二分图最大匹配做。

八、网络流

由于有其他做法（比如状压 DP），难度分仅供参考。

模拟费用流

2463. 最小移动总距离做到 $O ((n + m) \log (n + m))$

九、其他

1042. 不邻接植花 1712
1761. 一个图中连通三元组的最小度数 2005
2508. 添加边使所有节点度数都为偶数 2060
1579. 保证图可完全遍历 2132
2065. 最大化一张图中的路径价值 2178
1697. 检查边长度限制的路径是否存在 2300
2242. 节点序列的最大得分 2304
2493. 将节点分成尽可能多的组 2415 推荐
1782. 统计点对的数目 2457
3666. 使二进制字符串全为 1 的最少操作次数 2477 进阶 BFS / Gale-Ryser 定理
2612. 最少翻转操作数 2824 进阶 BFS
3435. 最短公共超序列的字母出现频率 3028
466. 统计重复个数做到 $O (| s_{1} | + | s_{2} |)$
LCP 16. 游乐园的游览计划
277. 搜寻名人（会员题）
1724. 检查边长度限制的路径是否存在 II（会员题）
2077. 殊途同归（会员题）三元环计数
3656. 判断是否存在简单图（会员题）Erdős–Gallai 定理

十、树上算法

见链表、树、回溯题单的第三章节。

关联题单

关于网格图的 DFS 和 BFS，见网格图题单。

算法题单

如何科学刷题？

如果你发现有题目可以补充进来，欢迎评论反馈。

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

一、图的遍历 ​

§1.1 深度优先搜索（DFS） ​

§1.2 广度优先搜索（BFS） ​

§1.3 图论建模 + BFS 最短路 ​

二、拓扑排序 ​

§2.1 拓扑排序 ​

§2.2 在拓扑序上 DP ​

§2.3 基环树 ​

三、最短路 ​

§3.1 单源最短路：Dijkstra 算法 ​

§3.2 全源最短路：Floyd 算法 ​

四、最小生成树 ​

五、欧拉路径/欧拉回路 ​

六、强连通分量/双连通分量 ​

七、二分图染色 ​

八、网络流 ​

九、其他 ​

十、树上算法 ​

关联题单 ​

算法题单 ​

一、图的遍历

§1.1 深度优先搜索（DFS）

§1.2 广度优先搜索（BFS）

§1.3 图论建模 + BFS 最短路

二、拓扑排序

§2.1 拓扑排序

§2.2 在拓扑序上 DP

§2.3 基环树

三、最短路

§3.1 单源最短路：Dijkstra 算法

§3.2 全源最短路：Floyd 算法

四、最小生成树

五、欧拉路径/欧拉回路

六、强连通分量/双连通分量

七、二分图染色

八、网络流

九、其他

十、树上算法

关联题单

算法题单