图的基本表示与遍历

一、图的基本概念

1.1 定义

图 ( G = (V, E) )，由顶点集 ( V ) 和边集 ( E ) 组成。

1.2 分类

类型	特性
有向图	边有方向
无向图	边无方向
加权图	边有权重
无权图	边无权重

二、图的表示

2.1 邻接矩阵

( n \times n ) 矩阵，( adj[i][j] = 1 ) 表示 ( i ) 到 ( j ) 有边。

int[][] adj = new int[n][n];
adj[u][v] = 1;  // u -> v 有边

优点：( O(1) ) 判断边是否存在
缺点：空间 ( O(n^2) )，稀疏图浪费

2.2 邻接表

每个顶点维护一个邻接顶点列表。

List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
adj[u].add(v);  // u -> v

优点：空间 ( O(V + E) )，适合稀疏图
缺点：判断边是否存在需遍历

三、深度优先搜索(DFS)

3.1 思想

沿着一条路径走到底，回溯后再走其他路径。

3.2 递归实现

boolean[] visited;

void dfs(int v, List<Integer>[] adj) {
    visited[v] = true;
    System.out.println(v);
    
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u, adj);
        }
    }
}

3.3 迭代实现

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

3.4 DFS应用

• 连通分量：统计图中的连通块
• 拓扑排序：检测有向环
• 路径搜索：找两点间路径

四、广度优先搜索(BFS)

4.1 思想

按层遍历，先访问所有邻居，再访问邻居的邻居。

4.2 实现

void bfs(int start, List<Integer>[] adj) {
    boolean[] 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.println(v);
        
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                queue.offer(u);
            }
        }
    }
}

4.3 BFS应用

• 最短路径：无权图的最短路径
• 层级遍历：社交网络中的”几度好友”

4.4 最短路径示例

public int shortestPath(List<Integer>[] adj, int start, int end) {
    boolean[] visited = new boolean[adj.length];
    Queue<int[]> queue = new LinkedList<>();  // [node, distance]
    queue.offer(new int[]{start, 0});
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int v = curr[0], dist = curr[1];
        
        if (v == end) return dist;
        
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                queue.offer(new int[]{u, dist + 1});
            }
        }
    }
    return -1;  // 不可达
}

五、DFS vs BFS

特性	DFS	BFS
数据结构	栈（递归/显式）	队列
空间复杂度	( O(h) )	( O(w) )
最短路径	不保证	保证（无权图）
适用场景	连通性、回溯、拓扑	最短路径、层级
实现	递归更简洁	迭代更自然

( h ) = 树高/图深度，( w ) = 最大宽度

六、图的环检测

6.1 无向图 - DFS

boolean hasCycle(int v, int parent, List<Integer>[] adj, boolean[] visited) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            if (hasCycle(u, v, adj, visited)) return true;
        } else if (u != parent) {
            return true;  // 遇到已访问且不是父节点
        }
    }
    return false;
}

6.2 有向图 - 三色标记法

// 0: 未访问, 1: 访问中, 2: 已访问
int[] state;

boolean hasCycleDirected(int v, List<Integer>[] adj) {
    if (state[v] == 1) return true;   // 遇到访问中的节点，有环
    if (state[v] == 2) return false;  // 已访问过，无环
    
    state[v] = 1;  // 标记为访问中
    for (int u : adj[v]) {
        if (hasCycleDirected(u, adj)) return true;
    }
    state[v] = 2;  // 标记为已访问
    return false;
}

七、总结

图是表达复杂关系的数据结构，邻接表是稀疏图的首选表示。DFS适合探索路径和连通性，BFS适合找最短路径。理解这两种遍历方式，是学习图算法的基础。