LeetCode图论算法全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 15:14:12

530

文章被收录于专栏：AI SPPECHAI SPPECH

一、图论基础概念

1.1 图的基本概念

图（Graph）是由顶点（Vertex）和边（Edge）组成的数据结构，用于表示元素之间的关系。在计算机科学中，图被广泛应用于网络分析、路径规划、社交网络等领域。

图的基本组成部分：

顶点（Vertex）：图中的节点，通常用字母或数字表示
边（Edge）：连接顶点的线段，表示顶点之间的关系
权重（Weight）：边的属性，可以表示距离、时间、成本等

1.2 图的分类

根据不同的标准，图可以分为以下几类：

无向图（Undirected Graph）：边没有方向，两个顶点之间可以互相访问
有向图（Directed Graph）：边有方向，两个顶点之间只能按照边的方向访问
加权图（Weighted Graph）：边带有权重
无权图（Unweighted Graph）：边没有权重
简单图（Simple Graph）：没有自环（连接同一个顶点的边）和重复边的图
多重图（Multigraph）：允许存在重复边的图
完全图（Complete Graph）：任意两个顶点之间都有一条边的图

1.3 图的表示方法

在计算机中，常用的图的表示方法有以下几种：

邻接矩阵（Adjacency Matrix）：使用二维数组来表示图，数组的行和列分别表示顶点，数组的值表示顶点之间是否有边
- 优点：查询两个顶点之间是否有边的时间复杂度为O(1)
- 缺点：空间复杂度为O(n²)，其中n是顶点的数量
邻接表（Adjacency List）：使用链表或数组来表示图，每个顶点对应一个链表，链表中存储与该顶点相邻的所有顶点
- 优点：空间复杂度为O(n + m)，其中n是顶点的数量，m是边的数量
- 缺点：查询两个顶点之间是否有边的时间复杂度为O(k)，其中k是与第一个顶点相邻的顶点的数量
边列表（Edge List）：使用列表来存储图中的所有边，每条边由两个顶点和权重（如果有的话）组成
- 优点：适合处理稀疏图，空间复杂度为O(m)
- 缺点：查询两个顶点之间是否有边的时间复杂度为O(m)

1.4 图的常见术语

在图论中，有一些常见的术语需要了解：

路径（Path）：从一个顶点到另一个顶点的一系列边
环（Cycle）：起点和终点相同的路径
简单路径（Simple Path）：路径中的顶点不重复出现
简单环（Simple Cycle）：环中的顶点不重复出现（除了起点和终点）
连通（Connected）：在无向图中，如果两个顶点之间有路径，则它们是连通的
强连通（Strongly Connected）：在有向图中，如果两个顶点之间可以互相到达，则它们是强连通的
连通分量（Connected Component）：无向图中最大的连通子图
强连通分量（Strongly Connected Component）：有向图中最大的强连通子图
度（Degree）：与一个顶点相连的边的数量
- 入度（In-Degree）：在有向图中，指向一个顶点的边的数量
- 出度（Out-Degree）：在有向图中，从一个顶点出发的边的数量

二、图的遍历算法

2.1 深度优先搜索（DFS）

深度优先搜索（Depth-First Search，DFS） 是一种用于遍历或搜索图的算法。它的基本思想是：从一个起始顶点出发，沿着一条路径一直走到底，直到不能再走为止，然后回溯到上一个顶点，继续沿着其他路径走到底，直到遍历完整个图。

DFS的应用场景包括：

判断图中是否有环
寻找图中的连通分量
拓扑排序
解决迷宫问题

实现方法：DFS可以使用递归或栈来实现。

// 使用递归实现DFS
public void dfs(int start, boolean[] visited, List<List<Integer>> graph) {
    // 标记当前顶点为已访问
    visited[start] = true;
    // 处理当前顶点
    System.out.print(start + " ");
    // 访问所有未访问的邻接顶点
    for (int neighbor : graph.get(start)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

// 使用栈实现DFS
public void dfsStack(int start, List<List<Integer>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    // 将起始顶点入栈
    stack.push(start);
    visited[start] = true;
    while (!stack.isEmpty()) {
        // 弹出栈顶顶点
        int current = stack.pop();
        // 处理当前顶点
        System.out.print(current + " ");
        // 将所有未访问的邻接顶点入栈
        for (int neighbor : graph.get(current)) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

2.2 广度优先搜索（BFS）

广度优先搜索（Breadth-First Search，BFS） 是一种用于遍历或搜索图的算法。它的基本思想是：从一个起始顶点出发，先访问所有与该顶点相邻的顶点，然后再依次访问这些顶点的邻接顶点，直到遍历完整个图。

BFS的应用场景包括：

寻找图中两个顶点之间的最短路径
层次遍历
判断图中是否有环

实现方法：BFS可以使用队列来实现。

// 使用队列实现BFS
public void bfs(int start, List<List<Integer>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    // 将起始顶点入队
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        // 出队
        int current = queue.poll();
        // 处理当前顶点
        System.out.print(current + " ");
        // 将所有未访问的邻接顶点入队
        for (int neighbor : graph.get(current)) {
            if (!visited[neighbor]) {
                queue.offer(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

2.3 岛屿数量（LeetCode 200）

题目描述：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

示例：输入： 11110 11010 11000 00000 输出：1

解题思路：我们可以使用DFS或BFS来解决这个问题。我们遍历网格中的每个单元格，如果该单元格是陆地（值为’1’）且未被访问过，那么我们就找到了一个新的岛屿，然后使用DFS或BFS来标记该岛屿的所有陆地单元格为已访问。

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int rows = grid.length;
    int cols = grid[0].length;
    int count = 0;
    // 遍历网格中的每个单元格
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 如果该单元格是陆地且未被访问过，找到了一个新的岛屿
            if (grid[i][j] == '1') {
                count++;
                // 使用DFS来标记该岛屿的所有陆地单元格
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

// 使用DFS来标记岛屿的所有陆地单元格
private void dfs(char[][] grid, int i, int j) {
    int rows = grid.length;
    int cols = grid[0].length;
    // 检查边界条件和当前单元格是否是陆地
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1') {
        return;
    }
    // 标记当前单元格为已访问（将其值设置为'0'）
    grid[i][j] = '0';
    // 访问四个方向的相邻单元格
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

2.4 克隆图（LeetCode 133）

题目描述：给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

示例：输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 解释：图中有 4 个节点。节点 1 的值是 1，它有两个邻居：节点 2 和 4 。节点 2 的值是 2，它有两个邻居：节点 1 和 3 。节点 3 的值是 3，它有两个邻居：节点 2 和 4 。节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

解题思路：我们可以使用DFS或BFS来解决这个问题。我们需要为每个节点创建一个新的节点，并将新节点的邻居设置为原节点邻居的新节点。为了避免重复创建节点，我们可以使用一个哈希表来存储原节点和新节点的映射关系。

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }
    // 使用哈希表来存储原节点和新节点的映射关系
    Map<Node, Node> map = new HashMap<>();
    // 使用DFS来克隆图
    return dfs(node, map);
}

private Node dfs(Node node, Map<Node, Node> map) {
    // 如果节点已经被克隆，直接返回克隆后的节点
    if (map.containsKey(node)) {
        return map.get(node);
    }
    // 创建新节点
    Node clone = new Node(node.val);
    // 将原节点和新节点的映射关系存储到哈希表中
    map.put(node, clone);
    // 克隆邻居节点
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, map));
    }
    return clone;
}

三、最短路径算法

3.1 最短路径算法的基本概念

最短路径算法是一种用于寻找图中两个顶点之间最短路径的算法。最短路径可以是指路径的边数最少，也可以是指路径的权重之和最小，具体取决于问题的定义。

常见的最短路径算法包括：

Dijkstra算法：用于寻找加权图中从一个起始顶点到其他所有顶点的最短路径，要求边的权重不能为负
Bellman-Ford算法：用于寻找加权图中从一个起始顶点到其他所有顶点的最短路径，允许边的权重为负，但不允许存在负权环
Floyd-Warshall算法：用于寻找加权图中所有顶点对之间的最短路径，允许边的权重为负，但不允许存在负权环
BFS算法：用于寻找无权图中从一个起始顶点到其他所有顶点的最短路径

3.2 Dijkstra算法

Dijkstra算法 是一种用于寻找加权图中从一个起始顶点到其他所有顶点的最短路径的算法。它的基本思想是：维护一个距离数组和一个优先队列，距离数组存储从起始顶点到其他顶点的当前最短距离，优先队列存储顶点和其到起始顶点的距离。每次从优先队列中取出距离最小的顶点，然后更新其邻接顶点的距离。

Dijkstra算法的应用场景包括：

地图导航中的最短路径规划
网络路由中的最优路径选择
机器人路径规划

实现方法：Dijkstra算法可以使用优先队列来实现。

// Dijkstra算法的实现
public int[] dijkstra(int start, int n, List<List<int[]>> graph) {
    // 距离数组，存储从起始顶点到其他顶点的最短距离
    int[] dist = new int[n];
    // 初始化距离数组，所有距离初始化为无穷大
    Arrays.fill(dist, Integer.MAX_VALUE);
    // 起始顶点到自己的距离为0
    dist[start] = 0;
    // 优先队列，存储顶点和其到起始顶点的距离，按照距离从小到大排序
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    // 将起始顶点加入优先队列
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        // 取出距离最小的顶点
        int[] current = pq.poll();
        int node = current[0];
        int distance = current[1];
        // 如果当前顶点的距离已经大于已知的最短距离，跳过
        if (distance > dist[node]) {
            continue;
        }
        // 更新邻接顶点的距离
        for (int[] neighbor : graph.get(node)) {
            int nextNode = neighbor[0];
            int weight = neighbor[1];
            // 计算从起始顶点经过当前顶点到邻接顶点的距离
            int newDist = dist[node] + weight;
            // 如果新的距离小于已知的最短距离，更新距离并将邻接顶点加入优先队列
            if (newDist < dist[nextNode]) {
                dist[nextNode] = newDist;
                pq.offer(new int[]{nextNode, newDist});
            }
        }
    }
    return dist;
}

3.3 网络延迟时间（LeetCode 743）

题目描述：有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例：输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2

解题思路：我们可以使用Dijkstra算法来解决这个问题。我们需要找到从节点K到其他所有节点的最短路径，然后取这些最短路径的最大值作为答案。如果存在某个节点无法到达，返回-1。

public int networkDelayTime(int[][] times, int n, int k) {
    // 构建图的邻接表表示
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] time : times) {
        int u = time[0];
        int v = time[1];
        int w = time[2];
        graph.get(u).add(new int[]{v, w});
    }
    // 使用Dijkstra算法计算从节点k到其他所有节点的最短距离
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{k, 0});
    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int node = current[0];
        int distance = current[1];
        if (distance > dist[node]) {
            continue;
        }
        for (int[] neighbor : graph.get(node)) {
            int nextNode = neighbor[0];
            int weight = neighbor[1];
            int newDist = dist[node] + weight;
            if (newDist < dist[nextNode]) {
                dist[nextNode] = newDist;
                pq.offer(new int[]{nextNode, newDist});
            }
        }
    }
    // 计算所有节点都收到信号所需的时间
    int maxTime = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) {
            // 存在某个节点无法到达
            return -1;
        }
        maxTime = Math.max(maxTime, dist[i]);
    }
    return maxTime;
}

3.4 最短路径总和（LeetCode 127）

题目描述：字典 wordList 中从单词 beginWord 到 endWord 的转换序列是一个按下述规格形成的序列：序列中第一个单词是 beginWord 。序列中相邻单词之间只有一个字母不同。序列中最后一个单词是 endWord 。序列中的所有单词都在 wordList 中。给你两个单词 beginWord 和 endWord 和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

示例：输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] 输出：5 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

解题思路：我们可以使用BFS来解决这个问题。我们可以将每个单词看作图中的一个顶点，如果两个单词之间只有一个字母不同，那么它们之间有一条边。然后，我们从beginWord开始进行BFS，直到找到endWord或者遍历完所有可能的单词。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    // 将wordList转换为集合，方便快速查找
    Set<String> wordSet = new HashSet<>(wordList);
    // 如果endWord不在wordList中，无法转换，返回0
    if (!wordSet.contains(endWord)) {
        return 0;
    }
    // 使用BFS来寻找最短转换序列
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    // 使用集合来记录已经访问过的单词，避免重复访问
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);
    // 转换序列的长度，初始值为1（包含beginWord）
    int length = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 遍历当前层的所有单词
        for (int i = 0; i < size; i++) {
            String currentWord = queue.poll();
            // 尝试改变currentWord的每个字符，看是否能得到endWord或其他在wordList中的单词
            char[] charArray = currentWord.toCharArray();
            for (int j = 0; j < charArray.length; j++) {
                char originalChar = charArray[j];
                // 尝试用a-z替换当前字符
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == originalChar) {
                        continue;
                    }
                    charArray[j] = c;
                    String newWord = new String(charArray);
                    // 如果得到endWord，返回转换序列的长度+1
                    if (newWord.equals(endWord)) {
                        return length + 1;
                    }
                    // 如果newWord在wordList中且未被访问过，将其加入队列和访问集合
                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        queue.offer(newWord);
                        visited.add(newWord);
                    }
                }
                // 恢复原字符
                charArray[j] = originalChar;
            }
        }
        // 每遍历完一层，转换序列的长度加1
        length++;
    }
    // 无法找到转换序列，返回0
    return 0;
}

四、最小生成树算法

4.1 最小生成树的基本概念

最小生成树（Minimum Spanning Tree，MST） 是指在一个连通的加权无向图中，找出一棵生成树，使得树上所有边的权重之和最小。生成树是指包含图中所有顶点的一棵树，也就是说，生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树（无环且连通）。

最小生成树的应用场景包括：

网络设计中的最小成本问题
城市规划中的道路铺设问题
电路设计中的最小连接问题

常见的最小生成树算法包括：

Kruskal算法：按照边的权重从小到大排序，依次选择边，如果选择的边不会形成环，则将其加入最小生成树
Prim算法：从一个起始顶点开始，每次选择一条与已选顶点相连的最小权重的边，将其加入最小生成树

4.2 Kruskal算法

Kruskal算法 是一种用于寻找加权无向图的最小生成树的算法。它的基本思想是：按照边的权重从小到大排序，然后依次考察这些边，如果加入这条边不会形成环，则将其加入最小生成树。为了判断加入一条边是否会形成环，我们可以使用并查集（Union-Find）数据结构。

实现方法：Kruskal算法的实现步骤如下：

将图中的所有边按照权重从小到大排序
初始化每个顶点为一个单独的集合
依次考察排序后的每条边，如果边的两个顶点不在同一个集合中，则将这条边加入最小生成树，并将这两个顶点所在的集合合并
重复步骤3，直到最小生成树包含所有顶点

// Kruskal算法的实现
public int kruskal(int n, int[][] edges) {
    // 按照边的权重从小到大排序
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    // 初始化并查集
    UnionFind uf = new UnionFind(n);
    // 最小生成树的总权重
    int totalWeight = 0;
    // 已经选择的边的数量
    int edgeCount = 0;
    // 依次考察排序后的每条边
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        // 如果边的两个顶点不在同一个集合中，加入这条边不会形成环
        if (uf.find(u) != uf.find(v)) {
            // 将这条边加入最小生成树
            totalWeight += weight;
            edgeCount++;
            // 合并这两个顶点所在的集合
            uf.union(u, v);
            // 如果已经选择了n-1条边，最小生成树已经形成
            if (edgeCount == n - 1) {
                break;
            }
        }
    }
    // 如果无法形成最小生成树（图不连通），返回-1
    if (edgeCount != n - 1) {
        return -1;
    }
    return totalWeight;
}

// 并查集数据结构
class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        // 初始化，每个顶点的父节点是自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 查找顶点x所在集合的代表元素（根节点）
    public int find(int x) {
        if (parent[x] != x) {
            // 路径压缩，将x的父节点直接设置为根节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并顶点x和顶点y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        // 按秩合并，将较小的树连接到较大的树上
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

4.3 Prim算法

Prim算法 是一种用于寻找加权无向图的最小生成树的算法。它的基本思想是：从一个起始顶点开始，维护一个集合包含已选顶点，然后每次选择一条连接已选顶点和未选顶点的最小权重的边，将其加入最小生成树，并将对应的未选顶点加入已选集合。重复这个过程，直到最小生成树包含所有顶点。

实现方法：Prim算法可以使用优先队列来实现。

// Prim算法的实现
public int prim(int n, List<List<int[]>> graph) {
    // 记录顶点是否已经加入最小生成树
    boolean[] visited = new boolean[n];
    // 最小生成树的总权重
    int totalWeight = 0;
    // 已经加入最小生成树的顶点的数量
    int count = 0;
    // 优先队列，存储边（目标顶点，权重），按照权重从小到大排序
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    // 从顶点0开始
    visited[0] = true;
    count++;
    // 将顶点0的所有边加入优先队列
    for (int[] edge : graph.get(0)) {
        pq.offer(edge);
    }
    while (!pq.isEmpty() && count < n) {
        // 取出权重最小的边
        int[] edge = pq.poll();
        int to = edge[0];
        int weight = edge[1];
        // 如果目标顶点已经加入最小生成树，跳过
        if (visited[to]) {
            continue;
        }
        // 将目标顶点加入最小生成树
        visited[to] = true;
        count++;
        totalWeight += weight;
        // 将目标顶点的所有边加入优先队列
        for (int[] nextEdge : graph.get(to)) {
            if (!visited[nextEdge[0]]) {
                pq.offer(nextEdge);
            }
        }
    }
    // 如果无法形成最小生成树（图不连通），返回-1
    if (count != n) {
        return -1;
    }
    return totalWeight;
}

4.4 最低成本连通所有城市（LeetCode 1135）

题目描述：想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。返回使得所有城市都连通所需的最低成本。如果根据已知条件无法连通所有城市，则请你返回 -1。

示例：输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]] 输出：6 解释：选择将城市 1 和城市 2 连接，成本为 5；将城市 1 和城市 3 连接，成本为 6；总成本为 11。但还有更好的选择：将城市 2 和城市 3 连接，成本为 1；然后将城市 1 和城市 2 连接，成本为 5；总成本为 6。

解题思路：我们可以使用Kruskal算法或Prim算法来解决这个问题。这是一个典型的最小生成树问题，我们需要找到一棵包含所有N个城市的生成树，使得生成树的总权重最小。

public int minimumCost(int N, int[][] connections) {
    // 使用Kruskal算法
    // 按照边的权重从小到大排序
    Arrays.sort(connections, (a, b) -> a[2] - b[2]);
    // 初始化并查集，注意城市编号是从1开始的
    UnionFind uf = new UnionFind(N + 1);
    // 最小生成树的总权重
    int totalCost = 0;
    // 已经选择的边的数量
    int edgeCount = 0;
    // 依次考察排序后的每条边
    for (int[] connection : connections) {
        int city1 = connection[0];
        int city2 = connection[1];
        int cost = connection[2];
        // 如果两个城市不在同一个集合中，加入这条边不会形成环
        if (uf.find(city1) != uf.find(city2)) {
            // 将这条边加入最小生成树
            totalCost += cost;
            edgeCount++;
            // 合并这两个城市所在的集合
            uf.union(city1, city2);
            // 如果已经选择了N-1条边，最小生成树已经形成
            if (edgeCount == N - 1) {
                break;
            }
        }
    }
    // 如果无法连通所有城市，返回-1
    if (edgeCount != N - 1) {
        return -1;
    }
    return totalCost;
}

// 并查集数据结构
class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        // 初始化，每个顶点的父节点是自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 查找顶点x所在集合的代表元素（根节点）
    public int find(int x) {
        if (parent[x] != x) {
            // 路径压缩，将x的父节点直接设置为根节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并顶点x和顶点y所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        // 按秩合并，将较小的树连接到较大的树上
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

五、拓扑排序算法

5.1 拓扑排序的基本概念

拓扑排序（Topological Sorting） 是一种对有向无环图（DAG）中的顶点进行排序的算法，使得对于图中的每条有向边 (u, v)，顶点u在排序结果中都出现在顶点v的前面。拓扑排序常用于解决依赖关系问题，如任务调度、课程安排等。

拓扑排序的应用场景包括：

任务调度：确定任务的执行顺序，确保每个任务在其依赖的任务完成后再执行
课程安排：确定课程的学习顺序，确保先学习先修课程
编译系统：确定源文件的编译顺序，确保先编译被依赖的文件

常见的拓扑排序算法包括：

Kahn算法：基于BFS，维护一个入度数组，每次选择入度为0的顶点，将其加入结果集，并更新其邻接顶点的入度
DFS算法：基于DFS，维护一个访问标记数组，在DFS完成时将顶点加入结果集，最后反转结果集

5.2 Kahn算法

Kahn算法 是一种用于对有向无环图进行拓扑排序的算法。它的基本思想是：维护一个入度数组，记录每个顶点的入度；维护一个队列，存储入度为0的顶点。每次从队列中取出一个顶点，将其加入结果集，并更新其邻接顶点的入度。如果某个邻接顶点的入度变为0，则将其加入队列。重复这个过程，直到队列为空。如果结果集中的顶点数量等于图中的顶点数量，则拓扑排序成功；否则，图中存在环，无法进行拓扑排序。

实现方法：Kahn算法可以使用队列来实现。

// Kahn算法的实现
public List<Integer> kahn(int n, List<List<Integer>> graph) {
    // 计算每个顶点的入度
    int[] inDegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            inDegree[v]++;
        }
    }
    // 初始化队列，将入度为0的顶点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    // 拓扑排序的结果
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        // 取出一个入度为0的顶点
        int u = queue.poll();
        // 将其加入结果集
        result.add(u);
        // 更新其邻接顶点的入度
        for (int v : graph.get(u)) {
            inDegree[v]--;
            // 如果邻接顶点的入度变为0，将其加入队列
            if (inDegree[v] == 0) {
                queue.offer(v);
            }
        }
    }
    // 如果结果集中的顶点数量等于图中的顶点数量，拓扑排序成功；否则，图中存在环
    if (result.size() != n) {
        return new ArrayList<>(); // 图中存在环，无法进行拓扑排序
    }
    return result;
}

5.3 课程表（LeetCode 207）

题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]。给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例：输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。

解题思路：我们可以使用Kahn算法来解决这个问题。这是一个典型的拓扑排序问题，我们需要判断是否存在一个拓扑排序，使得所有课程都可以被选修。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建图的邻接表表示
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    // 计算每个顶点的入度
    int[] inDegree = new int[numCourses];
    for (int[] prerequisite : prerequisites) {
        int course = prerequisite[0];
        int prerequisiteCourse = prerequisite[1];
        graph.get(prerequisiteCourse).add(course);
        inDegree[course]++;
    }
    // 初始化队列，将入度为0的顶点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    // 记录已经学习的课程数量
    int count = 0;
    while (!queue.isEmpty()) {
        // 取出一个入度为0的顶点（课程）
        int course = queue.poll();
        // 增加已学习的课程数量
        count++;
        // 更新其邻接顶点（后续课程）的入度
        for (int nextCourse : graph.get(course)) {
            inDegree[nextCourse]--;
            // 如果后续课程的入度变为0，将其加入队列
            if (inDegree[nextCourse] == 0) {
                queue.offer(nextCourse);
            }
        }
    }
    // 如果已经学习的课程数量等于总课程数量，说明可以完成所有课程的学习
    return count == numCourses;
}

5.4 课程表 II（LeetCode 210）

题目描述：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例：输入：2, [[1,0]] 输出：[0,1] 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

解题思路：我们可以使用Kahn算法来解决这个问题。这是一个典型的拓扑排序问题，我们需要找到一个拓扑排序，使得所有课程都可以被选修。如果无法找到这样的拓扑排序，返回一个空数组。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // 构建图的邻接表表示
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    // 计算每个顶点的入度
    int[] inDegree = new int[numCourses];
    for (int[] prerequisite : prerequisites) {
        int course = prerequisite[0];
        int prerequisiteCourse = prerequisite[1];
        graph.get(prerequisiteCourse).add(course);
        inDegree[course]++;
    }
    // 初始化队列，将入度为0的顶点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    // 拓扑排序的结果
    int[] result = new int[numCourses];
    int index = 0;
    while (!queue.isEmpty()) {
        // 取出一个入度为0的顶点（课程）
        int course = queue.poll();
        // 将其加入结果集
        result[index++] = course;
        // 更新其邻接顶点（后续课程）的入度
        for (int nextCourse : graph.get(course)) {
            inDegree[nextCourse]--;
            // 如果后续课程的入度变为0，将其加入队列
            if (inDegree[nextCourse] == 0) {
                queue.offer(nextCourse);
            }
        }
    }
    // 如果结果集中的顶点数量等于图中的顶点数量，拓扑排序成功；否则，图中存在环
    if (index != numCourses) {
        return new int[0]; // 无法完成所有课程
    }
    return result;
}

六、图论算法的高级应用

6.1 二分图判断（LeetCode 785）

题目描述：给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

示例：输入：[[1,3], [0,2], [1,3], [0,2]] 输出：true 解释：无向图如下： 0----1 | | | | 3----2 我们可以将节点分成两组: {0,2} 和 {1,3}。

解题思路：我们可以使用DFS或BFS来解决这个问题。我们尝试用两种颜色（如0和1）来标记图中的每个顶点，使得相邻的顶点颜色不同。如果我们能够成功地完成这个标记过程，那么图是二分图；否则，图不是二分图。

public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    // 使用数组来记录每个顶点的颜色，-1表示未染色，0和1表示两种不同的颜色
    int[] colors = new int[n];
    Arrays.fill(colors, -1);
    // 遍历每个顶点，对于未染色的顶点，使用BFS进行染色
    for (int i = 0; i < n; i++) {
        if (colors[i] == -1) {
            if (!bfs(graph, colors, i)) {
                return false;
            }
        }
    }
    return true;
}

// 使用BFS进行染色
private boolean bfs(int[][] graph, int[] colors, int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    colors[start] = 0; // 初始颜色为0
    while (!queue.isEmpty()) {
        int current = queue.poll();
        // 遍历当前顶点的所有邻接顶点
        for (int neighbor : graph[current]) {
            // 如果邻接顶点未染色，将其染成与当前顶点不同的颜色
            if (colors[neighbor] == -1) {
                colors[neighbor] = colors[current] ^ 1; // 异或操作，0变1，1变0
                queue.offer(neighbor);
            } else if (colors[neighbor] == colors[current]) {
                // 如果邻接顶点已经染色，且颜色与当前顶点相同，图不是二分图
                return false;
            }
        }
    }
    return true;
}

6.2 寻找桥接边（LeetCode 1192）

题目描述：在一个连通的无向图中，桥接边是指移除该边后，图不再连通。给定一个连通的无向图，返回其所有的桥接边。

示例：输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] 输出：[[1,3]] 解释：边 [1,3] 是桥接边，因为移除它后，图不再连通。

解题思路：我们可以使用Tarjan算法来解决这个问题。Tarjan算法的基本思想是：使用DFS遍历图，维护每个顶点的发现时间（disc）和能够回溯到的最早顶点的发现时间（low）。对于一条边（u, v），如果low[v] > disc[u]，则这条边是桥接边。

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    // 构建图的邻接表表示
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (List<Integer> connection : connections) {
        int u = connection.get(0);
        int v = connection.get(1);
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    // 存储桥接边
    List<List<Integer>> bridges = new ArrayList<>();
    // 用于Tarjan算法的数组
    int[] disc = new int[n]; // 顶点的发现时间
    int[] low = new int[n];  // 顶点能够回溯到的最早顶点的发现时间
    boolean[] visited = new boolean[n]; // 顶点是否被访问过
    int[] time = {0}; // 当前时间
    // 对每个未访问的顶点进行DFS
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            tarjan(graph, i, -1, disc, low, visited, time, bridges);
        }
    }
    return bridges;
}

// Tarjan算法
private void tarjan(List<List<Integer>> graph, int u, int parent, int[] disc, int[] low, boolean[] visited, int[] time, List<List<Integer>> bridges) {
    // 标记当前顶点为已访问
    visited[u] = true;
    // 设置当前顶点的发现时间和能够回溯到的最早顶点的发现时间
    disc[u] = low[u] = ++time[0];
    // 遍历当前顶点的所有邻接顶点
    for (int v : graph.get(u)) {
        // 如果邻接顶点是父顶点，跳过
        if (v == parent) {
            continue;
        }
        // 如果邻接顶点未被访问过
        if (!visited[v]) {
            tarjan(graph, v, u, disc, low, visited, time, bridges);
            // 更新当前顶点能够回溯到的最早顶点的发现时间
            low[u] = Math.min(low[u], low[v]);
            // 判断边（u, v）是否是桥接边
            if (low[v] > disc[u]) {
                bridges.add(Arrays.asList(u, v));
            }
        } else {
            // 如果邻接顶点已经被访问过，更新当前顶点能够回溯到的最早顶点的发现时间
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}

6.3 寻找强连通分量（LeetCode 2150）

题目描述：在一个有向图中，强连通分量是指最大的子图，其中任意两个顶点都可以互相到达。给定一个有向图，返回其所有的强连通分量。

示例：输入：n = 5, edges = [[0,1],[1,2],[2,0],[3,4]] 输出：[[0,1,2],[3],[4]] 解释：顶点0、1、2可以互相到达，形成一个强连通分量。顶点3和顶点4各自形成一个强连通分量。

解题思路：我们可以使用Kosaraju算法来解决这个问题。Kosaraju算法的基本思想是：首先对图进行DFS，记录顶点的完成顺序；然后按照完成顺序的逆序，对转置图（所有边的方向反转后的图）进行DFS，每次DFS访问到的顶点构成一个强连通分量。

public List<List<Integer>> findStronglyConnectedComponents(int n, List<List<Integer>> edges) {
    // 构建图的邻接表表示
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (List<Integer> edge : edges) {
        int u = edge.get(0);
        int v = edge.get(1);
        graph.get(u).add(v);
    }
    // 第一次DFS，记录顶点的完成顺序
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs1(graph, i, visited, stack);
        }
    }
    // 构建转置图
    List<List<Integer>> transposeGraph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        transposeGraph.add(new ArrayList<>());
    }
    for (List<Integer> edge : edges) {
        int u = edge.get(0);
        int v = edge.get(1);
        transposeGraph.get(v).add(u);
    }
    // 第二次DFS，按照完成顺序的逆序，对转置图进行DFS，找出所有强连通分量
    Arrays.fill(visited, false);
    List<List<Integer>> result = new ArrayList<>();
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (!visited[u]) {
            List<Integer> component = new ArrayList<>();
            dfs2(transposeGraph, u, visited, component);
            result.add(component);
        }
    }
    return result;
}

// 第一次DFS，记录顶点的完成顺序
private void dfs1(List<List<Integer>> graph, int u, boolean[] visited, Stack<Integer> stack) {
    visited[u] = true;
    for (int v : graph.get(u)) {
        if (!visited[v]) {
            dfs1(graph, v, visited, stack);
        }
    }
    // 在DFS完成时，将顶点加入栈中
    stack.push(u);
}

// 第二次DFS，找出强连通分量
private void dfs2(List<List<Integer>> graph, int u, boolean[] visited, List<Integer> component) {
    visited[u] = true;
    component.add(u);
    for (int v : graph.get(u)) {
        if (!visited[v]) {
            dfs2(graph, v, visited, component);
        }
    }
}

6.4 旅行商问题（TSP）

题目描述：旅行商问题（Traveling Salesman Problem，TSP）是指一个旅行商要访问n个城市，每个城市只能访问一次，最后回到出发城市。要求找出一条路径，使得总路程最短。

示例：输入：n = 4, distances = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]] 输出：80 解释：最短路径是 0 -> 1 -> 3 -> 2 -> 0，总路程为10 + 25 + 30 + 15 = 80。

解题思路：旅行商问题是一个NP难问题，没有多项式时间的算法。对于小规模的问题，我们可以使用动态规划来解决。动态规划的状态可以表示为（当前所在城市，已访问的城市集合），状态转移方程为：dp[mask][u] = min(dp[mask][u], dp[mask ^ (1 << u)][v] + distances[v][u])，其中mask是一个位掩码，表示已访问的城市集合。

public int tsp(int n, int[][] distances) {
    // 状态数为2^n * n，其中mask表示已访问的城市集合，u表示当前所在的城市
    int[][] dp = new int[1 << n][n];
    // 初始化所有状态为无穷大
    for (int[] row : dp) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }
    // 初始状态：从城市0出发，已访问的城市只有城市0
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 0;
    }
    // 遍历所有可能的状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            // 如果城市u未被访问过，跳过
            if ((mask & (1 << u)) == 0) {
                continue;
            }
            // 遍历所有可能的前一个城市v
            for (int v = 0; v < n; v++) {
                // 如果城市v未被访问过，或者v == u，跳过
                if ((mask & (1 << v)) == 0 || u == v) {
                    continue;
                }
                // 从状态mask ^ (1 << u)（即已访问的城市集合为mask，不包括城市u）转移到状态mask
                if (dp[mask ^ (1 << u)][v] != Integer.MAX_VALUE) {
                    dp[mask][u] = Math.min(dp[mask][u], dp[mask ^ (1 << u)][v] + distances[v][u]);
                }
            }
        }
    }
    // 找出所有城市都被访问过，并且回到出发城市0的最短路径
    int result = Integer.MAX_VALUE;
    for (int u = 1; u < n; u++) {
        if (dp[(1 << n) - 1][u] != Integer.MAX_VALUE) {
            result = Math.min(result, dp[(1 << n) - 1][u] + distances[u][0]);
        }
    }
    return result;
}

七、图论算法的优化技巧总结

7.1 图的表示优化

在实际应用中，我们需要根据图的特点选择合适的表示方法：

稠密图：如果图中的边数接近n²，其中n是顶点的数量，那么使用邻接矩阵可以获得更好的性能
稀疏图：如果图中的边数远小于n²，那么使用邻接表可以获得更好的空间效率
边权为非负整数：可以使用数组来代替HashMap，提高查询效率

7.2 算法选择优化

在解决图论问题时，我们需要根据问题的特点选择合适的算法：

寻找最短路径：
- 边权为非负：使用Dijkstra算法
- 边权有负但无负权环：使用Bellman-Ford算法
- 所有顶点对之间的最短路径：使用Floyd-Warshall算法
- 无权图：使用BFS
寻找最小生成树：
- 稠密图：使用Prim算法
- 稀疏图：使用Kruskal算法
拓扑排序：
- 有向无环图：使用Kahn算法或DFS算法
连通性问题：
- 无向图的连通分量：使用DFS或BFS
- 有向图的强连通分量：使用Kosaraju算法或Tarjan算法

7.3 常见的优化技巧

剪枝：在搜索过程中，提前判断某些情况，避免不必要的计算
位运算：使用位运算来表示集合，提高空间效率和运算速度
优先队列：使用优先队列来维护候选顶点，提高算法的效率
并查集：使用并查集来处理连通性问题，提高算法的效率
记忆化搜索：使用记忆化搜索来避免重复计算
双向BFS：从起点和终点同时开始BFS，提高搜索效率

7.4 常见的错误和陷阱

越界问题：在访问图的顶点或边时，需要注意数组的边界条件，避免越界访问
重复访问问题：在遍历图时，需要使用访问标记来避免重复访问顶点
环的处理问题：在某些算法中，如拓扑排序，需要特别注意环的处理
图的连通性问题：在解决某些问题时，需要先判断图是否连通
边的方向问题：在处理有向图时，需要特别注意边的方向

八、总结与展望

图论算法是计算机科学中的重要组成部分，它在网络分析、路径规划、社交网络等领域有着广泛的应用。在本文中，我们介绍了图论的基本概念、图的表示方法、图的遍历算法、最短路径算法、最小生成树算法、拓扑排序算法以及图论算法的高级应用。

图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS），它们是解决图论问题的基础。最短路径算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法，它们用于寻找图中两个顶点之间的最短路径。最小生成树算法包括Kruskal算法和Prim算法，它们用于寻找加权无向图的最小生成树。拓扑排序算法包括Kahn算法和DFS算法，它们用于对有向无环图进行拓扑排序。

在实际应用中，我们需要根据问题的特点选择合适的图的表示方法和算法，并通过剪枝、位运算、优先队列、并查集、记忆化搜索等优化技巧来提高算法的效率。同时，我们也需要注意避免越界、重复访问、环的处理等常见的错误和陷阱。

随着计算机科学的发展，图论算法也在不断地演进和优化。例如，在大数据领域，图论算法与并行计算、分布式计算等技术相结合，以应对大规模数据的挑战。此外，图论算法也被广泛应用于机器学习、数据挖掘等领域，如图神经网络（GNN）的兴起，为图数据的处理提供了新的思路和方法。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除

队列