图的存储与遍历

图是最灵活也最复杂的数据结构。选择合适的存储方式（邻接矩阵/邻接表/边列表）和遍历策略（DFS/BFS）是解决所有图论问题的基础。

一、图的分类

Mermaid · 渲染中（下方为源码）

graph LR
  G[图] --> M[邻接矩阵]
  G --> L[邻接表]
  G --> E[边列表]
  M --> A[稠密图友好]
  L --> B[稀疏图友好]

维度	类型
方向	有向图 / 无向图
权重	有权图 / 无权图
连通性	连通图 / 非连通图
特殊	DAG、完全图、二分图、树

二、存储方式

邻接矩阵

int[][] adj = new int[n][n]; // adj[i][j] = 权重（0 表示无边）
// 适合稠密图，空间 O(V²)

邻接表

List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
// 加边
adj[u].add(v);
adj[v].add(u); // 无向图
// 适合稀疏图，空间 O(V+E)

边列表

int[][] edges = new int[m][3]; // {from, to, weight}
// 适合 Kruskal、Bellman-Ford 等按边操作的算法

图是最灵活也最复杂的数据结构。选择合适的存储方式（邻接矩阵/邻接表/边列表）和遍历策略（DFS/BFS）是解决所有图论问题的基础。

一、图的分类

Mermaid · 渲染中（下方为源码）

graph LR
  G[图] --> M[邻接矩阵]
  G --> L[邻接表]
  G --> E[边列表]
  M --> A[稠密图友好]
  L --> B[稀疏图友好]

维度	类型
方向	有向图 / 无向图
权重	有权图 / 无权图
连通性	连通图 / 非连通图
特殊	DAG、完全图、二分图、树

二、存储方式

邻接矩阵

int[][] adj = new int[n][n]; // adj[i][j] = 权重（0 表示无边）
// 适合稠密图，空间 O(V²)

邻接表

List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
// 加边
adj[u].add(v);
adj[v].add(u); // 无向图
// 适合稀疏图，空间 O(V+E)

边列表

int[][] edges = new int[m][3]; // {from, to, weight}
// 适合 Kruskal、Bellman-Ford 等按边操作的算法

场景	推荐
稠密图（E ≈ V²）	邻接矩阵
稀疏图（E << V²）	邻接表
需要排序所有边	边列表
需要快速判断边存在	邻接矩阵 / HashSet

boolean[] visited;

void dfs(int u, List<Integer>[] adj) {
    visited[u] = true;
    // 处理节点 u
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj);
        }
    }
}

// 非连通图：遍历所有连通分量
for (int i = 0; i < n; i++) {
    if (!visited[i]) dfs(i, adj);
}

void dfsIterative(int start, List<Integer>[] adj) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) stack.push(v);
        }
    }
}

int[] bfs(int start, List<Integer>[] adj) {
    int n = adj.length;
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist; // 最短距离（无权图）
}

维度	DFS	BFS
数据结构	栈（递归）	队列
遍历顺序	深入到底再回溯	逐层扩展
最短路径	❌（无权图）	✅（无权图）
连通分量	✅	✅
拓扑排序	✅（后序）	✅（Kahn）
环检测	✅（回边）	✅（入度）
空间	O(V)（递归栈）	O(V)（队列）

问题	方法
岛屿数量（200）	DFS/BFS 标记连通分量
课程表（207/210）	拓扑排序（BFS/DFS）
单词接龙（127）	BFS 最短路
克隆图（133）	DFS/BFS + HashMap
二分图判定（785）	DFS/BFS 染色

图的存储与遍历

一、图的分类

二、存储方式

邻接矩阵

邻接表

边列表

图的存储与遍历 Graph Storage & Traversal

一、图的分类

二、存储方式

邻接矩阵

邻接表

边列表

图的存储与遍历 Graph Storage & Traversal

选择建议

三、DFS（深度优先搜索）

迭代 DFS

四、BFS（广度优先搜索）

五、DFS vs BFS

六、经典应用

七、面试要点

相关教程

交互式可视化