图数据结构

一、什么是图

由顶点和边组成：G = (V, E)。

二、分类

• 有向图 / 无向图。
• 有权图 / 无权图。
• 连通图 / 非连通图。

三、存储方式

邻接矩阵

int[][] graph = new int[n][n];

空间 O(n²)，查询快。

邻接表

List<List<Integer>> adj = new ArrayList<>();

空间 O(n+e)，省空间。

四、遍历

BFS

队列，一层层。

DFS

递归/栈，一条路走到黑。

五、应用

• 最短路径（Dijkstra）。
• 拓扑排序。
• 判断有环。
• 并查集。

高频

邻接表最常用。BFS/DFS 必会。