图：邻接矩阵、邻接表与 Java 实现

重新整理“图：邻接矩阵、邻接表与 Java 实现”时，我先翻了自己以前的错误记录，其中最典型的一条就是：邻接矩阵和邻接表的概念不难，但真正写 Java 实现时，空间、遍历方式和边对象设计会带来完全不同的使用体验。沿着这个问题再看原理和代码，比直接背结论清楚得多。

图由顶点集合 V 和边集合 E 组成。代码实现最重要的不是类名，而是让数据表示与查询模式匹配。

邻接矩阵

图的邻接矩阵、邻接表和 BFS 分层图

图：表示方式决定空间成本，BFS 使用队列按层访问

public final class MatrixGraph {
    private final int[][] weights;

    public MatrixGraph(int vertices) {
        weights = new int[vertices][vertices];
    }

    public void addUndirectedEdge(int a, int b, int weight) {
        weights[a][b] = weight;
        weights[b][a] = weight;
    }

    public boolean adjacent(int a, int b) {
        return weights[a][b] != 0;
    }
}

这里用 0 表示无边，就无法表达权重为 0 的合法边。更稳妥的实现可使用特殊哨兵、布尔矩阵加权重矩阵，或 Optional 风格封装。无向图写入时必须对称更新两个位置。

邻接表

public final class AdjacencyListGraph {
    public record Edge(int to, int weight) {}
    private final java.util.List<java.util.List<Edge>> adjacency;

    public AdjacencyListGraph(int vertices) {
        adjacency = new java.util.ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) adjacency.add(new java.util.ArrayList<>());
    }

    public void addDirectedEdge(int from, int to, int weight) {
        adjacency.get(from).add(new Edge(to, weight));
    }

    public java.util.List<Edge> neighbors(int vertex) {
        return java.util.List.copyOf(adjacency.get(vertex));
    }
}

返回不可变副本可以避免调用方越过图的规则直接篡改内部边，但大型图频繁复制会有成本。生产接口可返回只读视图、迭代器或流式访问，并清楚约定生命周期。

重复边、删除与索引

邻接表使用 List 时，重复添加同一条边会并存；使用 Map 可以让 to 唯一，并方便更新权重：

private final java.util.List<java.util.Map<Integer, Integer>> adjacency;

public void putEdge(int from, int to, int weight) {
    checkVertex(from);
    checkVertex(to);
    adjacency.get(from).put(to, weight);
}

public boolean removeEdge(int from, int to) {
    return adjacency.get(from).remove(to) != null;
}

无向图的添加和删除必须同时修改两个方向，最好封装在一个原子方法中。若中途失败或被并发读取，就可能看到半条边，所以共享可变图需要锁、不可变快照或单线程所有权。

BFS：无权图最短边数

public int[] distancesFrom(int start) {
    int[] distance = new int[adjacency.size()];
    java.util.Arrays.fill(distance, -1);
    java.util.ArrayDeque<Integer> queue = new java.util.ArrayDeque<>();
    distance[start] = 0;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (Edge edge : adjacency.get(current)) {
            if (distance[edge.to()] != -1) continue;
            distance[edge.to()] = distance[current] + 1;
            queue.offer(edge.to());
        }
    }
    return distance;
}

节点在入队时标记，能避免多个前驱把同一节点重复入队。BFS 的时间复杂度在邻接表上是 O(V+E)，在矩阵上需要扫描每行，通常是 O(V²)。

若要恢复具体路径，再维护 previous[next] = current，从终点反向追踪到起点后翻转。

DFS、连通分量与环

public java.util.List<Integer> depthFirst(int start) {
    boolean[] visited = new boolean[adjacency.size()];
    java.util.ArrayList<Integer> order = new java.util.ArrayList<>();
    java.util.ArrayDeque<Integer> stack = new java.util.ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int current = stack.pop();
        if (visited[current]) continue;
        visited[current] = true;
        order.add(current);
        var neighbors = adjacency.get(current);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            stack.push(neighbors.get(i).to());
        }
    }
    return order;
}

无向图检测环时，访问到已访问邻居不一定是环，它可能只是当前节点的父节点；有向图则需要三色状态：未访问、当前递归路径、已完成。遇到“当前路径”节点才说明存在有向环。

拓扑排序

Kahn 算法先统计每个顶点入度，把入度为 0 的顶点入队。每取出一个顶点，就移除它的出边并减少邻居入度。最终处理顶点数小于总数，说明图中有环。

static java.util.List<Integer> topological(Graph graph) {
    int[] indegree = graph.indegrees();
    java.util.ArrayDeque<Integer> queue = new java.util.ArrayDeque<>();
    for (int i = 0; i < indegree.length; i++) if (indegree[i] == 0) queue.offer(i);
    java.util.ArrayList<Integer> order = new java.util.ArrayList<>();
    while (!queue.isEmpty()) {
        int current = queue.poll();
        order.add(current);
        for (Edge edge : graph.neighbors(current)) {
            if (--indegree[edge.to()] == 0) queue.offer(edge.to());
        }
    }
    if (order.size() != indegree.length) throw new IllegalStateException("cycle");
    return order;
}

拓扑顺序通常不唯一。若业务需要稳定输出，可以让零入度容器使用优先队列，并定义明确的键顺序。

非负权最短路 Dijkstra

Dijkstra 每次确认当前距离最小的未完成顶点，再松弛它的出边。优先队列中可存在同一顶点的多个距离快照，出队时若不是当前最佳距离就丢弃。

record State(int vertex, long distance) {}

static long[] dijkstra(Graph graph, int start) {
    long[] dist = new long[graph.size()];
    java.util.Arrays.fill(dist, Long.MAX_VALUE);
    dist[start] = 0;
    var queue = new java.util.PriorityQueue<State>(
            java.util.Comparator.comparingLong(State::distance));
    queue.offer(new State(start, 0));
    while (!queue.isEmpty()) {
        State state = queue.poll();
        if (state.distance() != dist[state.vertex()]) continue;
        for (Edge edge : graph.neighbors(state.vertex())) {
            if (edge.weight() < 0) throw new IllegalArgumentException("negative edge");
            long candidate = state.distance() + edge.weight();
            if (candidate < dist[edge.to()]) {
                dist[edge.to()] = candidate;
                queue.offer(new State(edge.to(), candidate));
            }
        }
    }
    return dist;
}

还要防止距离加法溢出，并明确不可达点的表示。

DFS 与递归深度

DFS 可以递归实现，但超大图可能超过线程栈。显式 ArrayDeque 更容易控制深度。无向图检测环时要区分“访问过的父节点”和真正的回边；有向图检测环则常用三色状态区分未访问、当前路径和已完成。

实现前必须定下的规则

顶点用连续整数还是业务 ID？业务 ID 可先映射为紧凑索引。
重复添加同一条边是覆盖、累加还是并存？
删除顶点时怎样处理关联边？
图是否允许负权、自环和并行边？
是否需要线程安全或版本快照？

一个“能跑”的 Graph 类如果没有这些约定，很快会在算法结果和业务语义之间产生歧义。

测试清单

空图、单顶点、自环、重复边和不连通图。
有向与无向添加删除是否符合规则。
BFS 距离与路径恢复。
DFS 在含环图中不会无限循环。
拓扑排序验证每条边的前后顺序，并检测环。
Dijkstra 覆盖不可达点、零权边、大权重和负权拒绝。
矩阵与邻接表在同一图上的遍历结果一致。