图的存储与基础

图（Graph）是一种复杂的非线性数据结构，由顶点（Vertex）和边（Edge）组成。图可以表示多对多的关系，广泛应用于社交网络、地图导航、网页链接等场景。

基本概念

图的定义

图 G 由两个集合组成：

• V(G)：顶点的有限非空集合
• E(G)：边的有限集合

形式化表示为 $G = (V, E)$，其中 V 是顶点集，E 是边集。

图的类型

类型	定义	示例
无向图	边没有方向，(u, v) 和 (v, u) 是同一条边	社交网络中的好友关系
有向图	边有方向，<u, v> 和 <v, u> 是不同的边	网页之间的链接关系
加权图	边带有权值	地图中的距离
连通图	无向图中任意两个顶点之间都有路径	-
强连通图	有向图中任意两个顶点之间都有双向路径	-
完全图	任意两个顶点之间都有边	-

基本术语

术语	定义
顶点的度	与该顶点相连的边的数量
入度（有向图）	指向该顶点的边的数量
出度（有向图）	从该顶点指出的边的数量
路径	从一个顶点到另一个顶点的边序列
简单路径	路径中不重复出现顶点
环	起点和终点相同的路径
连通分量	无向图中的极大连通子图
生成树	包含所有顶点的极小连通子图

图的存储结构

邻接矩阵

使用二维数组存储顶点之间的边关系。

public class AdjacencyMatrixGraph {
    private int[][] matrix;      // 邻接矩阵
    private int numVertices;     // 顶点数量
    private boolean directed;    // 是否为有向图
    
    public AdjacencyMatrixGraph(int numVertices, boolean directed) {
        this.numVertices = numVertices;
        this.directed = directed;
        this.matrix = new int[numVertices][numVertices];
        
        // 初始化为无穷大（表示无边）
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (i != j) {
                    matrix[i][j] = Integer.MAX_VALUE;
                } else {
                    matrix[i][j] = 0;  // 自己到自己为 0
                }
            }
        }
    }
    
    // 添加边 - O(1)
    public void addEdge(int from, int to, int weight) {
        matrix[from][to] = weight;
        if (!directed) {
            matrix[to][from] = weight;  // 无向图对称
        }
    }
    
    // 判断是否有边 - O(1)
    public boolean hasEdge(int from, int to) {
        return matrix[from][to] != Integer.MAX_VALUE && matrix[from][to] != 0;
    }
    
    // 获取边的权重 - O(1)
    public int getWeight(int from, int to) {
        return matrix[from][to];
    }
    
    // 获取邻接顶点 - O(V)
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            if (hasEdge(vertex, i)) {
                neighbors.add(i);
            }
        }
        return neighbors;
    }
    
    // 获取顶点的度
    public int getDegree(int vertex) {
        int degree = 0;
        for (int i = 0; i < numVertices; i++) {
            if (hasEdge(vertex, i)) {
                degree++;
            }
        }
        return degree;
    }
}

邻接矩阵的特点：

优点	缺点
判断两顶点是否有边：O(1)	空间复杂度：O(V²)
适合稠密图	添加/删除顶点需要改变数组大小
矩阵运算方便	遍历邻接顶点需要 O(V)

解释：

• 对于稀疏图（边数远小于 V²），邻接矩阵会浪费大量空间
• 邻接矩阵适合边比较多的稠密图
• 矩阵可以用位运算优化空间

邻接表

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

public class AdjacencyListGraph {
    private static class Edge {
        int to;         // 目标顶点
        int weight;     // 权重
        Edge next;      // 下一条边
        
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
            this.next = null;
        }
    }
    
    private Edge[] adjacencyList;  // 邻接表
    private int numVertices;
    private boolean directed;
    
    public AdjacencyListGraph(int numVertices, boolean directed) {
        this.numVertices = numVertices;
        this.directed = directed;
        this.adjacencyList = new Edge[numVertices];
    }
    
    // 添加边 - O(1)
    public void addEdge(int from, int to, int weight) {
        // 头插法添加边
        Edge edge = new Edge(to, weight);
        edge.next = adjacencyList[from];
        adjacencyList[from] = edge;
        
        // 无向图添加反向边
        if (!directed) {
            Edge reverseEdge = new Edge(from, weight);
            reverseEdge.next = adjacencyList[to];
            adjacencyList[to] = reverseEdge;
        }
    }
    
    // 判断是否有边 - O(degree)
    public boolean hasEdge(int from, int to) {
        Edge edge = adjacencyList[from];
        while (edge != null) {
            if (edge.to == to) {
                return true;
            }
            edge = edge.next;
        }
        return false;
    }
    
    // 获取邻接顶点 - O(degree)
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        Edge edge = adjacencyList[vertex];
        while (edge != null) {
            neighbors.add(edge.to);
            edge = edge.next;
        }
        return neighbors;
    }
    
    // 获取顶点的度 - O(degree)
    public int getDegree(int vertex) {
        int degree = 0;
        Edge edge = adjacencyList[vertex];
        while (edge != null) {
            degree++;
            edge = edge.next;
        }
        return degree;
    }
}

邻接表的特点：

优点	缺点
空间复杂度：O(V + E)	判断两顶点是否有边：O(degree)
适合稀疏图	获取边的权重需要遍历
遍历邻接顶点高效	不适合需要随机访问边的场景

两种存储方式对比

操作	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V + E)
判断是否有边	O(1)	O(degree)
遍历邻接顶点	O(V)	O(degree)
添加边	O(1)	O(1)
删除边	O(1)	O(degree)
适合场景	稠密图	稀疏图

选择建议：

• 如果图是稠密的（边数接近 V²），使用邻接矩阵
• 如果图是稀疏的（边数远小于 V²），使用邻接表
• 如果需要频繁判断两点是否相邻，使用邻接矩阵
• 如果需要频繁遍历邻接顶点，使用邻接表

图的遍历

深度优先搜索（DFS）

从起点出发，沿着一条路径尽可能深入，直到无法继续，然后回溯。

核心思想：DFS 使用栈（或递归）来实现"走到尽头再回头"的遍历策略。

public class GraphDFS {
    private AdjacencyListGraph graph;
    private boolean[] visited;
    
    public GraphDFS(AdjacencyListGraph graph) {
        this.graph = graph;
    }
    
    // DFS 递归实现
    public void dfs(int start) {
        visited = new boolean[graph.numVertices];
        dfsRecursive(start);
    }
    
    private void dfsRecursive(int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");  // 访问顶点
        
        // 遍历邻接顶点
        for (int neighbor : graph.getNeighbors(vertex)) {
            if (!visited[neighbor]) {
                dfsRecursive(neighbor);
            }
        }
    }
    
    // DFS 迭代实现（使用栈）
    public void dfsIterative(int start) {
        visited = new boolean[graph.numVertices];
        Deque<Integer> stack = new ArrayDeque<>();
        
        stack.push(start);
        visited[start] = true;
        
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.print(vertex + " ");
            
            // 逆序入栈，保证按顺序访问
            List<Integer> neighbors = graph.getNeighbors(vertex);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }
}

DFS 的应用：

1. 检测连通分量

public int countConnectedComponents(AdjacencyListGraph graph) {
    int count = 0;
    boolean[] visited = new boolean[graph.numVertices];
    
    for (int i = 0; i < graph.numVertices; i++) {
        if (!visited[i]) {
            dfsComponent(graph, i, visited);
            count++;
        }
    }
    
    return count;
}

private void dfsComponent(AdjacencyListGraph graph, int vertex, boolean[] visited) {
    visited[vertex] = true;
    for (int neighbor : graph.getNeighbors(vertex)) {
        if (!visited[neighbor]) {
            dfsComponent(graph, neighbor, visited);
        }
    }
}

2. 检测环

public boolean hasCycle(AdjacencyListGraph graph) {
    boolean[] visited = new boolean[graph.numVertices];
    boolean[] recursionStack = new boolean[graph.numVertices];
    
    for (int i = 0; i < graph.numVertices; i++) {
        if (!visited[i]) {
            if (dfsCycle(graph, i, visited, recursionStack)) {
                return true;
            }
        }
    }
    
    return false;
}

private boolean dfsCycle(AdjacencyListGraph graph, int vertex, 
                         boolean[] visited, boolean[] recursionStack) {
    visited[vertex] = true;
    recursionStack[vertex] = true;
    
    for (int neighbor : graph.getNeighbors(vertex)) {
        if (!visited[neighbor]) {
            if (dfsCycle(graph, neighbor, visited, recursionStack)) {
                return true;
            }
        } else if (recursionStack[neighbor]) {
            return true;  // 发现环
        }
    }
    
    recursionStack[vertex] = false;
    return false;
}

3. 拓扑排序

拓扑排序用于解决依赖关系问题，如课程安排、编译顺序等。拓扑排序只适用于有向无环图（DAG）。

public List<Integer> topologicalSort(AdjacencyListGraph graph) {
    boolean[] visited = new boolean[graph.numVertices];
    LinkedList<Integer> result = new LinkedList<>();
    
    for (int i = 0; i < graph.numVertices; i++) {
        if (!visited[i]) {
            dfsTopo(graph, i, visited, result);
        }
    }
    
    return result;
}

private void dfsTopo(AdjacencyListGraph graph, int vertex, 
                     boolean[] visited, LinkedList<Integer> result) {
    visited[vertex] = true;
    
    for (int neighbor : graph.getNeighbors(vertex)) {
        if (!visited[neighbor]) {
            dfsTopo(graph, neighbor, visited, result);
        }
    }
    
    result.addFirst(vertex);  // 逆后序排列
}

解释：

• 拓扑排序的结果是顶点的一个线性序列，满足所有边的方向
• 应用场景：任务调度、编译依赖、课程安排

广度优先搜索（BFS）

从起点出发，先访问所有邻接顶点，再访问邻接顶点的邻接顶点。

核心思想：BFS 使用队列实现"层层推进"的遍历策略，先访问距离近的顶点。

public class GraphBFS {
    private AdjacencyListGraph graph;
    
    public GraphBFS(AdjacencyListGraph graph) {
        this.graph = graph;
    }
    
    // BFS 实现
    public void bfs(int start) {
        boolean[] visited = new boolean[graph.numVertices];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    // BFS 求最短路径（无权图）
    public int[] shortestPath(int start) {
        int[] distance = new int[graph.numVertices];
        Arrays.fill(distance, -1);
        
        Queue<Integer> queue = new LinkedList<>();
        distance[start] = 0;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[vertex] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        return distance;
    }
    
    // 获取路径
    public List<Integer> getPath(int start, int end) {
        int[] parent = new int[graph.numVertices];
        Arrays.fill(parent, -1);
        boolean[] visited = new boolean[graph.numVertices];
        
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            
            if (vertex == end) {
                return reconstructPath(parent, start, end);
            }
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = vertex;
                    queue.offer(neighbor);
                }
            }
        }
        
        return Collections.emptyList();  // 没有路径
    }
    
    private List<Integer> reconstructPath(int[] parent, int start, int end) {
        LinkedList<Integer> path = new LinkedList<>();
        int current = end;
        
        while (current != -1) {
            path.addFirst(current);
            current = parent[current];
        }
        
        return path;
    }
}

BFS 的特点：

• 按层次遍历，先访问距离近的顶点
• 可以求无权图的最短路径
• 使用队列实现

为什么 BFS 能保证最短路径？

BFS 按"层"扩展，先访问距离起点为 1 的节点，再访问距离为 2 的节点，以此类推。当第一次访问到终点时，一定是最短路径。

DFS 与 BFS 对比

特性	DFS	BFS
数据结构	栈（递归）	队列
空间复杂度	O(V)（递归栈深度）	O(V)（队列大小）
时间复杂度	O(V + E)	O(V + E)
适用场景	路径查找、拓扑排序、检测环	最短路径、层次遍历
遍历顺序	深入优先	层次优先

图的遍历与算法

图的遍历（DFS/BFS）、最短路径（Dijkstra/Floyd）、最小生成树（Prim/Kruskal）等算法已移至专门章节：

• 图的遍历与拓扑排序
• 最短路径算法
• 最小生成树

经典问题

1. 岛屿数量 (LeetCode 200)

使用 DFS 或 BFS 搜索连通分量。

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

解释：

• 遍历网格，遇到 '1' 就进行 DFS，将连通的 '1' 都变成 '0'
• 每次 DFS 完成后，岛屿数量加 1

2. 课程表（拓扑排序）

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建图和入度数组
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    // BFS 拓扑排序（Kahn 算法）
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return count == numCourses;
}

解释：

• 使用 Kahn 算法（BFS）进行拓扑排序
• 如果能完成拓扑排序（count == numCourses），说明没有环，可以完成所有课程

3. 克隆图 (LeetCode 133)

public Node cloneGraph(Node node) {
    if (node == null) return null;
    
    Map<Node, Node> visited = new HashMap<>();
    return dfsClone(node, visited);
}

private Node dfsClone(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }
    
    Node clone = new Node(node.val, new ArrayList<>());
    visited.put(node, clone);
    
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfsClone(neighbor, visited));
    }
    
    return clone;
}

4. 判断二分图 (LeetCode 785)

public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];  // 0: 未着色, 1: 颜色1, -1: 颜色2
    
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!bfsColor(graph, i, color)) {
                return false;
            }
        }
    }
    return true;
}

private boolean bfsColor(int[][] graph, int start, int[] color) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    color[start] = 1;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph[node]) {
            if (color[neighbor] == 0) {
                color[neighbor] = -color[node];
                queue.offer(neighbor);
            } else if (color[neighbor] == color[node]) {
                return false;  // 相邻节点颜色相同
            }
        }
    }
    return true;
}

解释：

• 二分图是指可以将图的顶点分成两个集合，使得每条边的两个端点分别属于不同的集合
• 使用 BFS 或 DFS 进行染色，如果相邻节点颜色相同则不是二分图

小结

本章我们学习了：

1. 图的表示：邻接矩阵、邻接表
2. 图的遍历：DFS、BFS
3. 图的应用：连通分量、环检测、拓扑排序、最短路径
4. 经典问题：岛屿数量、课程表、克隆图、二分图判断

图是最复杂的数据结构之一，掌握图的存储和遍历是解决图问题的基础。

练习

1. 实现图的邻接矩阵和邻接表存储
2. LeetCode 200：岛屿数量
3. LeetCode 207：课程表
4. LeetCode 210：课程表 II
5. LeetCode 133：克隆图
6. LeetCode 785：判断二分图
7. LeetCode 743：网络延迟时间