图是数据结构中最后一类重要的非线性结构。前面的链表是一对一，树是一对多，图是多对多。图的遍历（DFS/BFS）和最小生成树是 408 考研的重点。

一、图的基本概念

1. 定义

图由**顶点（Vertex）和边（Edge）**组成。

无向图：
   A —— B
   |    |
   C —— D

有向图（带箭头）：
   A → B
   ↓    ↓
   C ← D

术语：

• 顶点：图中的节点
• 边：顶点之间的连线
• 无向图：边没有方向，(A, B) = (B, A)
• 有向图：边有方向，<A, B> ≠ <B, A>
• 完全图：任意两个顶点之间都有边
• 权：边上的数值（如距离、花费）
• 连通图：任意两个顶点之间都有路径可达

二、图的存储结构

1. 邻接矩阵

// 用一个二维数组存储顶点之间的邻接关系
// graph[i][j] = 1 表示顶点 i 到 j 有边
// graph[i][j] = 0 表示没有边

public class GraphMatrix {
    private int[][] matrix;  // 邻接矩阵
    private int n;           // 顶点数
    private boolean directed; // 是否有向

    public GraphMatrix(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        matrix = new int[n][n];
    }

    // 添加边
    public void addEdge(int i, int j, int weight) {
        matrix[i][j] = weight;        // i → j
        if (!directed) {
            matrix[j][i] = weight;    // 无向图对称
        }
    }

    // 判断是否有边
    public boolean hasEdge(int i, int j) {
        return matrix[i][j] != 0;
    }
}

无向图的邻接矩阵（对称）：
     A  B  C  D
  A [0, 1, 1, 0]
  B [1, 0, 0, 1]
  C [1, 0, 0, 1]
  D [0, 1, 1, 0]

优点： 判断两点是否有边 O(1)，实现简单
缺点： 占用空间 O(n²)，稀疏图浪费空间

2. 邻接表

// 每个顶点维护一个链表，存储与其相连的顶点

public class GraphList {
    private List<Integer>[] adj;  // 邻接表数组
    private int n;

    public GraphList(int n) {
        this.n = n;
        adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
    }

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

    public List<Integer> getNeighbors(int v) {
        return adj[v];
    }
}

无向图的邻接表：
  A → [B, C]
  B → [A, D]
  C → [A, D]
  D → [B, C]

优点： 节省空间 O(n + e)，适合稀疏图
缺点： 判断两点是否有边需要遍历链表 O(degree)

3. 邻接矩阵 vs 邻接表

对比	邻接矩阵	邻接表
空间	O(n²)	O(n + e)
判边	O(1) 🏆	O(度)
遍历邻居	O(n)	O(度) 🏆
适合	稠密图	稀疏图（常用） 🏆

三、图的遍历

1. 深度优先搜索（DFS）

沿着一条路走到黑，走不通了再回头。

public class GraphDFS {

    private List<Integer>[] adj;
    private boolean[] visited;

    public void dfs(int start) {
        visited = new boolean[adj.length];
        dfsRecursive(start);
    }

    private void dfsRecursive(int v) {
        visited[v] = true;
        System.out.print(v + " ");  // 访问当前顶点

        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfsRecursive(neighbor);  // 递归访问未访问的邻居
            }
        }
    }
}

从 A 开始 DFS（假设邻接顺序从小到大）：
  A → B → D → C
  路径：A → B → D → C

  访问顺序：A, B, D, C

时间复杂度： O(n + e)
空间复杂度： O(n)（递归栈）

2. 广度优先搜索（BFS）

一层一层往外扩，像水的波纹。

public class GraphBFS {

    private List<Integer>[] adj;
    private boolean[] visited;

    public void bfs(int start) {
        visited = new boolean[adj.length];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");  // 访问当前顶点

            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);  // 未访问的邻居入队
                }
            }
        }
    }
}

从 A 开始 BFS：
  第一层：A
  第二层：B, C
  第三层：D

  访问顺序：A, B, C, D

时间复杂度： O(n + e)
空间复杂度： O(n)（队列）

3. DFS vs BFS

对比	DFS	BFS
数据结构	栈（递归）	队列
遍历顺序	沿着路径深入	逐层扩展
适用场景	连通性判断、拓扑排序	最短路径、层序遍历
实现难度	递归，代码简洁	循环，稍复杂

四、最小生成树

用最小的总权值把所有顶点连通。

1. Prim 算法

从一个顶点开始，每次找权值最小的边加入。

public class Prim {

    /**
     * Prim 算法求最小生成树
     * @param graph 邻接矩阵（权值，0表示无边）
     * @return 最小总权值
     */
    public static int prim(int[][] graph) {
        int n = graph.length;
        int[] lowCost = new int[n];   // 到各顶点的最小权值
        boolean[] visited = new boolean[n];
        int total = 0;

        // 从顶点0开始
        visited[0] = true;
        for (int i = 0; i < n; i++) {
            lowCost[i] = graph[0][i] == 0 ? Integer.MAX_VALUE : graph[0][i];
        }

        for (int i = 1; i < n; i++) {
            // 找权值最小的未访问顶点
            int min = Integer.MAX_VALUE;
            int minIdx = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && lowCost[j] < min) {
                    min = lowCost[j];
                    minIdx = j;
                }
            }

            if (minIdx == -1) break;  // 不连通

            visited[minIdx] = true;
            total += min;

            // 更新 lowCost
            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[minIdx][j] != 0
                    && graph[minIdx][j] < lowCost[j]) {
                    lowCost[j] = graph[minIdx][j];
                }
            }
        }
        return total;
    }
}

2. Kruskal 算法

每次选权值最小的边，只要不形成环就加入。

public class Kruskal {

    // 边的定义
    static class Edge implements Comparable<Edge> {
        int u, v, weight;
        public int compareTo(Edge o) { return this.weight - o.weight; }
    }

    // 并查集
    static class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[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]));
        }
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;
            parent[rx] = ry;
            return true;
        }
    }

    public static int kruskal(Edge[] edges, int n) {
        Arrays.sort(edges);                        // 按权值排序
        UnionFind uf = new UnionFind(n);
        int total = 0, count = 0;

        for (Edge e : edges) {
            if (uf.union(e.u, e.v)) {              // 不会形成环
                total += e.weight;
                count++;
                if (count == n - 1) break;          // n个顶点需要n-1条边
            }
        }
        return total;
    }
}

3. Prim vs Kruskal

对比	Prim	Kruskal
策略	选顶点	选边
数据结构	邻接矩阵	边集 + 并查集
时间复杂度	O(n²)	O(e log e)
适合	稠密图 🏆	稀疏图 🏆

五、408 考研经典考题

题1：邻接矩阵转邻接表

List<Integer>[] matrixToList(int[][] matrix) {
    int n = matrix.length;
    List<Integer>[] adj = new List[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                adj[i].add(j);
            }
        }
    }
    return adj;
}

题2：判断图是否连通

boolean isConnected(List<Integer>[] adj) {
    int n = adj.length;
    boolean[] visited = new boolean[n];
    dfs(adj, visited, 0);
    for (boolean v : visited) {
        if (!v) return false;
    }
    return true;
}

题3：拓扑排序

有向无环图（DAG）的顶点线性排序，AOV 网中活动执行的先后顺序。

// 核心思想：不断删除入度为 0 的顶点
List<Integer> topologicalSort(List<Integer>[] adj) {
    int n = adj.length;
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) {
        for (int v : adj[i]) inDegree[v]++;
    }

    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()) {
        int v = queue.poll();
        result.add(v);
        for (int neighbor : adj[v]) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

六、图的常见考点

1. 有 n 个顶点的无向完全图有 n(n-1)/2 条边
2. 有 n 个顶点的有向完全图有 n(n-1) 条边
3. 连通图至少需要 n-1 条边（树）
4. 图的邻接矩阵是对称矩阵（无向图）

DFS/BFS 时间复杂度的写法：
  邻接矩阵：O(n²)
  邻接表：O(n + e)

---

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。