图简介 graph intro

老马啸西风2025年10月1日大约 3 分钟

一、图的基本概念

在力扣中，“图”通常指由 顶点（Nodes / Vertices） 和 边（Edges） 组成的数据结构。图可以是：

有向图（Directed Graph）：边有方向，例如 A -> B 表示只能从 A 到 B。
无向图（Undirected Graph）：边无方向，例如 A - B 表示 A 可以到 B，B 也可以到 A。
带权图（Weighted Graph）：边有权重（cost、距离等）。
无权图（Unweighted Graph）：边没有权重。

其他重要概念：

度（Degree）：一个顶点的边数。
- 有向图中分为入度和出度。
邻居（Neighbor / Adjacent Node）：直接相连的节点。
连通性（Connectivity）：图是否为连通图，即是否所有节点之间都可达。
环（Cycle）：起点和终点相同的一条路径。

二、图的存储方式

在力扣题目中，图的输入通常有三种方式：

1. 邻接矩阵（Adjacency Matrix）

用二维数组表示图，matrix[i][j] 表示顶点 i 到顶点 j 是否有边或边的权重。
优点：快速查询是否有边，复杂度 O(1)。
缺点：空间复杂度高，O(V²)。

int[][] graph = {
    {0, 1, 0},
    {1, 0, 1},
    {0, 1, 0}
};

2. 邻接表（Adjacency List）

每个顶点存储一个邻居列表。
优点：节省空间，特别适合稀疏图。
力扣题目中最常用。

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(0).add(1); // 0 -> 1
graph.get(1).add(0); // 1 -> 0 (无向)

3. 边列表（Edge List）

存储边的集合 (u, v) 或 (u, v, w)。
常用于最小生成树算法（Kruskal）。

int[][] edges = {{0,1},{1,2},{0,2}};

三、图的遍历

力扣图题中最常用的两种遍历：

1. 广度优先搜索（BFS）

按层遍历图。
常用 队列（Queue） 实现。
用于：
- 最短路径（无权图）
- 分层问题
- 二分图检测

Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;

while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            queue.offer(neighbor);
        }
    }
}

2. 深度优先搜索（DFS）

尽可能深地访问图。
用于：
- 连通性
- 拓扑排序
- 回溯
- 检测环

boolean[] visited = new boolean[n];

void dfs(int node) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) dfs(neighbor);
    }
}

四、图的常用算法

力扣图题中高频算法：

1. 最短路径

无权图：BFS
带权图：
- Dijkstra（非负权）
- Bellman-Ford（可处理负权）
- Floyd-Warshall（任意两点最短路径）

2. 拓扑排序（Topological Sort）

有向无环图（DAG）常用。
方法：
- BFS + 入度数组（Kahn 算法）
- DFS + 栈

3. 并查集（Union Find）

用于判断连通性、环、岛屿数量等。
力扣题目如：
- LC200. 岛屿数量
- LC684. 冗余连接

4. 最小生成树（MST）

Kruskal 或 Prim
常用于带权无向图

5. 检测环

无向图：DFS + parent 判断
有向图：DFS + 访问状态（白/灰/黑）

6. 二分图检测

BFS/DFS + 染色
力扣题目：
- LC785. 判断二分图

五、力扣图题的输入类型示例

力扣上图题输入通常是：

二维数组（邻接矩阵/边列表）
- LC207. 课程表 int[][] prerequisites
邻接表形式
- LC207. 课程表也可

节点类（Node 对象）

LC133. 克隆图

class Node {
    public int val;
    public List<Node> neighbors;
}

六、力扣经典图题分类

类别	代表题	常用算法
BFS	LC127 单词接龙	BFS
DFS	LC695 岛屿数量	DFS
拓扑排序	LC207 课程表	BFS/DFS
并查集	LC200 岛屿数量	Union-Find
最短路径	LC743 网络延迟时间	Dijkstra
最小生成树	LC1584 连接所有点的最小费用	Kruskal / Prim
克隆图	LC133 克隆图	DFS/BFS

总结：

力扣图题核心是遍历与路径问题。
熟练掌握 BFS、DFS 是基础。
根据题目选择合适的存储方式（邻接表、邻接矩阵、边列表）。
高阶题目会涉及拓扑排序、并查集、最短路径、最小生成树等。

贡献者

bbhou