经典算法专栏 #01：图算法

图由顶点和边组成，是描述"关系"最自然的数据结构。本文覆盖图的存储、BFS/DFS 搜索、Dijkstra/Bellman-Ford 最短路径、Prim/Kruskal 最小生成树和拓扑排序，每个算法配有过程图辅助理解。

目录

图的基本概念

图（Graph） 由顶点（Vertex） 和边（Edge） 组成，顶点可以与任意其他顶点建立连接关系。

图的存储

同一张图可以用邻接矩阵或邻接表存储，二者的空间和时间取舍截然不同：

邻接矩阵

用二维数组 A[V][V] 存储，A[i][j] 表示顶点 i 到顶点 j 的边权（无边时为 0 或 ∞）：

int[][] graph = new int[V][V];
// 无向图：双向赋值
graph[i][j] = 1;
graph[j][i] = 1;
// 带权图：存权重
graph[i][j] = weight;

邻接表

每个顶点对应一个链表，只存储实际存在的邻居：

public class Graph {
    private final int v;
    private final LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) adj[i] = new LinkedList<>();
    }

    public void addEdge(int s, int t) { // 无向图
        adj[s].add(t);
        adj[t].add(s);
    }
}

升级版邻接表：将链表替换为红黑树、跳表或散列表，提升查询效率。如微博关注关系用跳表还能支持按用户名排序分页。

选型对比

BFS 广度优先搜索

广度优先搜索（BFS） 用队列驱动，从起点向外逐层扩散，先访问距离为 1 的邻居，再访问距离为 2 的……

关键性质：BFS 找到的路径是边数最少的路径（最短路径，无权图）。

实现

public void bfs(int s, int t) {
    if (s == t) return;
    boolean[] visited = new boolean[v];
    int[] prev = new int[v];         // prev[i] = 到达 i 的前驱节点
    Arrays.fill(prev, -1);

    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty()) {
        int w = queue.poll();
        for (int q : adj[w]) {
            if (!visited[q]) {
                prev[q] = w;
                if (q == t) {
                    printPath(prev, s, t); // 找到目标，打印路径
                    return;
                }
                visited[q] = true;
                queue.add(q);
            }
        }
    }
}

private void printPath(int[] prev, int s, int t) {
    if (prev[t] != -1 && t != s) printPath(prev, s, prev[t]);
    System.out.print(t + " ");
}

三个辅助变量的作用：

复杂度

DFS 深度优先搜索

深度优先搜索（DFS） 沿一条路走到底，走不通则回溯换路，本质上是递归调用栈的深度优先遍历。

关键性质：DFS 找到的路径不保证是最短路径，但能遍历图中所有可达顶点。

实现

private boolean found = false;

public void dfs(int s, int t) {
    boolean[] visited = new boolean[v];
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    recurDfs(s, t, visited, prev);
    if (found) printPath(prev, s, t);
}

private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
    if (found) return;
    visited[w] = true;
    if (w == t) { found = true; return; }
    for (int q : adj[w]) {
        if (!visited[q]) {
            prev[q] = w;
            recurDfs(q, t, visited, prev);
        }
    }
    // 此处隐式回溯：从 w 的所有邻居返回后，w 标记已访问但不影响其他路径
}

复杂度

BFS vs DFS 对比

最短路径

Dijkstra 算法

适用于无负权边的带权图，求单源最短路径。

核心思路：贪心。维护 dist[] 数组记录起点到每个顶点的当前最短距离，每次从未处理的顶点中取 dist 最小的，用它松弛所有邻居。

松弛操作：若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]。

public int[] dijkstra(int src) {
    int[] dist = new int[v];
    boolean[] processed = new boolean[v];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // 优先队列：(distance, vertex)
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[1];
        if (processed[u]) continue;
        processed[u] = true;

        for (int[] edge : adjWeighted[u]) { // [neighbor, weight]
            int neighbor = edge[0], weight = edge[1];
            if (dist[u] + weight < dist[neighbor]) {
                dist[neighbor] = dist[u] + weight;
                pq.offer(new int[]{dist[neighbor], neighbor});
            }
        }
    }
    return dist;
}

Bellman-Ford 算法

适用于有负权边的图，可检测负权环。

核心思路：对所有边做 V−1 轮松弛。第 k 轮结束后，dist[v] 是从源点经过至多 k 条边的最短距离。若第 V 轮仍能松弛，说明存在负权环。

public int[] bellmanFord(int src) {
    int[] dist = new int[v];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int i = 0; i < v - 1; i++) {        // V-1 轮
        for (int[] edge : edges) {            // 遍历所有边 (u, v, w)
            int u = edge[0], nv = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[nv])
                dist[nv] = dist[u] + w;
        }
    }
    // 检测负权环：若第 V 轮仍能松弛则有负权环
    for (int[] edge : edges) {
        if (dist[edge[0]] + edge[2] < dist[edge[1]])
            throw new RuntimeException("存在负权环");
    }
    return dist;
}

最短路径算法对比

最小生成树

最小生成树（MST）：在连通无向带权图中，找一棵包含所有 V 个顶点、仅用 V−1 条边、且边权之和最小的树。

Prim 算法

思路：从任意顶点出发，维护"已选集合 S"，每次选择连接 S 与非 S 的最小权边，将新顶点并入 S，重复 V−1 次。

S = {start}
重复 V-1 次：
  在所有 (u, v) 边中，u ∈ S，v ∉ S，选权重最小的边
  将 v 加入 S，记录边 (u, v)

• 时间：O(V²)，优先队列优化后 O((V+E) log V)
• 适合稠密图（E ≈ V²，优先队列优势不明显）

Kruskal 算法

思路：将所有边按权重从小到大排序，依次考察每条边——若加入后不形成环，则纳入 MST。用并查集判断成环。

public List<int[]> kruskal(int v, int[][] edges) {
    // edges: [u, v, weight]，按 weight 排序
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    int[] parent = new int[v];
    for (int i = 0; i < v; i++) parent[i] = i;

    List<int[]> mst = new ArrayList<>();
    for (int[] edge : edges) {
        int pu = find(parent, edge[0]);
        int pv = find(parent, edge[1]);
        if (pu != pv) {           // 不在同一连通分量，不成环
            mst.add(edge);
            parent[pu] = pv;      // 合并并查集
        }
        if (mst.size() == v - 1) break;
    }
    return mst;
}

private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]); // 路径压缩
    return parent[x];
}

• 时间：O(E log E)（排序主导）
• 适合稀疏图

Prim vs Kruskal

拓扑排序

拓扑排序：对有向无环图（DAG）的顶点进行线性排序，使每条边 (u→v) 中 u 都排在 v 之前。

典型应用：编译依赖、任务调度、课程先修关系、Makefile 构建顺序。

Kahn 算法（BFS + 入度）

public List<Integer> topoSort(int v, int[][] edges) {
    int[] inDegree = new int[v];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < v; i++) adj.add(new ArrayList<>());

    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        inDegree[e[1]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < v; i++)
        if (inDegree[i] == 0) queue.add(i); // 所有入度为 0 的顶点入队

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        result.add(u);
        for (int neighbor : adj.get(u)) {
            if (--inDegree[neighbor] == 0) // 入度归零，可以入队
                queue.add(neighbor);
        }
    }

    // 若结果不包含所有顶点，说明图中存在环（无法完成拓扑排序）
    if (result.size() < v) throw new RuntimeException("图中存在环，不是 DAG");
    return result;
}

步骤：

1. 统计所有顶点的入度
2. 将入度为 0 的顶点加入队列
3. 出队一个顶点 u，将其所有邻居的入度减 1；若某邻居入度变为 0，入队
4. 重复直到队列为空

DFS 拓扑排序

DFS 完成后逆序输出即为拓扑序（后处理时间越大的顶点排越前），适合递归场景：

public List<Integer> topoSortDFS(int v, List<List<Integer>> adj) {
    boolean[] visited = new boolean[v];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < v; i++)
        if (!visited[i]) dfsHelper(i, adj, visited, stack);
    List<Integer> result = new ArrayList<>(stack); // 栈顶 = 拓扑序第一个
    return result;
}

private void dfsHelper(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> stack) {
    visited[u] = true;
    for (int neighbor : adj.get(u))
        if (!visited[neighbor]) dfsHelper(neighbor, adj, visited, stack);
    stack.push(u); // 所有后继处理完后才入栈
}

参考资料

• 《数据结构与算法之美》— 第 30、31、43、44 章
• 图算法可视化（VisuAlgo）