图的存储与基础

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

基本概念

图的定义

图 G 由两个集合组成：

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

图的类型

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

基本术语

        A --- B
       /|    /|
      / |   / |
     C--+--D  |
     |  |  |  |
     |  E--+--F
     | /   | /
     |/    |/
     G-----H

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

图的存储结构

邻接矩阵

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

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)
适合场景	稠密图	稀疏图

图的遍历

深度优先搜索（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 的应用：

检测连通分量

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);
        }
    }
}

检测环

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;
}

拓扑排序

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);  // 逆后序排列
}

解释：

拓扑排序只适用于有向无环图（DAG）
结果是顶点的一个线性序列，满足所有边的方向
应用：任务调度、编译依赖

广度优先搜索（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 的特点：

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

图的遍历与算法

图的遍历（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);
}

练习

实现邻接矩阵和邻接表两种存储结构。
LeetCode 200：岛屿数量。
LeetCode 133：克隆图。
LeetCode 785：判断二分图。

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 拓扑排序
    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;
}

小结

本章我们学习了：

图的表示：邻接矩阵、邻接表
图的遍历：DFS、BFS
最短路径：Dijkstra、Floyd-Warshall
最小生成树：Prim、Kruskal
拓扑排序：DAG 的线性排序

练习

实现图的邻接矩阵和邻接表存储
LeetCode 200：岛屿数量
LeetCode 207：课程表
LeetCode 210：课程表 II
LeetCode 743：网络延迟时间
LeetCode 785：判断二分图

基本概念​

图的定义​

图的类型​

基本术语​

图的存储结构​

邻接矩阵​

邻接表​

两种存储方式对比​

图的遍历​

深度优先搜索（DFS）​

广度优先搜索（BFS）​

图的遍历与算法​

经典问题​

1. 岛屿数量 (LeetCode 200)​

练习​

2. 课程表（拓扑排序）​

小结​

练习​