1. 图是什么：先用生活场景搞懂图和图论术语
数据结构里“图”这个东西，初次接触的人往往有两种极端感受：一种觉得它不就是一堆点和线连在一起嘛，有什么好学的；另一种是被术语劝退，什么有向图、无向图、权值、度、连通分量，背了一堆名词还是不知道怎么用。我当年学的时候，属于第二种，直到后来做了几个涉及路径规划和依赖关系的实际项目，才真正把图这章吃透。
先说人话版本：图就是由顶点和边组成的一种结构，适合表达“多对多”的关系。你手机里的导航地图，每个路口是一个顶点，每条道路是一条边，道路的长度、拥堵程度就是边的权值。微信好友关系同样可以建模成一张图，每个人是一个顶点，两个人认识就在他俩之间连一条边。树其实也是图的一种特例，一棵树就相当于一张“没有环的无向连通图”。但图比树更自由，树有严格的父子层级，图里任意两个顶点之间都可以直接产生联系，这也是它表达能力强的根本原因。
然后再把术语逐个说清楚，方便后面对号入座：
- 无向图：边没有方向，A和B之间的边就代表“互相有关系”，比如好友关系、道路连通。
- 有向图：边有方向，A到B的边不一定能反向走，比如微博的关注关系、程序里模块的调用关系。
- 带权图：每条边上带一个数值，比如距离、时间、成本、带宽。不带权的话可以认为权值都为1。
- 度：无向图中顶点连接的边的数量。有向图中分为入度和出度，入度是“指向该顶点”的边的数量，出度是“从该顶点指出”的边的数量。
- 路径与回路：从一个顶点走到另一个顶点经过的边的序列叫路径；如果路径的起点和终点是同一个顶点，就叫回路或环。
- 连通与连通分量：无向图中，任意两个顶点之间都存在路径就叫连通图；不连通的话，拆出来的每一块就是连通分量。
这些术语别死记，你拿一张真实的城市地铁图对着看一遍就全记住了。地铁站的换乘关系是有向的还是无向的？从A站到B站通常能反向坐回来，所以是无向图；每条线路的行驶时间可以看作边的权值。你在哪一站下车能直达目的地，本质上就是在一个带权无向图里找最短路径。
图能做的事远不止这些。从网络路由到任务调度，从社交推荐到物流配送，甚至编译器里的依赖分析、代码评审里的调用链分析，底层都在用图。所以学图，学的不只是数据结构本身，更是一种把复杂关系“建模”出来的能力。
至于适合谁看，我直接说：如果你是正在学数据结构的在校生，这篇文章能帮你把图和树、数组、链表这些基础数据结构串起来；如果你是在职工程师想补算法功底，图的存储和遍历代码可以直接抄去改造；如果你是准备面试，那最短路径和拓扑排序是最高频的考点，我会把思路和代码都拆开讲。
2. 图的存储：邻接矩阵和邻接表到底怎么选
图建好了，存在内存里最常用的方案就两种：邻接矩阵和邻接表。很多人一开始纠结选哪个，其实判断标准就一条——图是稠密还是稀疏。
2.1 邻接矩阵：简单直观，但空间开销大
邻接矩阵是用一个二维数组来存图。假设图里有n个顶点，就开一个n乘n的矩阵，第i行第j列的值表示顶点i到顶点j之间有没有边，有边记1，无边记0。如果是带权图，就把权值填进去，没有边的位置用一个特殊值表示，比如整数最大值。
头一次接触的人会觉得这方法实在太“笨”了，但它的优势很实在：判断任意两个顶点是否直接相连，时间复杂度是O(1)，数组按下标访问就行；想遍历某个顶点的所有邻居，也只需要扫描对应的一整行。写起来也简单，二十行代码就能搞定。
代价就是空间。n个顶点需要n平方个存储单元，100个顶点就要1万个单元，1000个顶点就要100万个单元。如果一个图只有几百条边，大多数格子都是浪费的。所以邻接矩阵只适合顶点少、边很多的稠密图，比如一个班级内所有人都互相认识的关系网，或者一个区域内道路密集的路网。
2.2 邻接表：稀疏图的更优解
邻接表的思路很直接：每个顶点用一个链表或一个动态数组，把和它直接相连的邻居都记下来。整个图就是一个长度为n的数组，每个数组元素指向一个装着邻居信息的列表。
这样空间复杂度是O(V+E)，V是顶点数，E是边数。边的数量远少于顶点平方的稀疏图，用邻接表能省下大把内存。实际开发里，绝大多数场景都是稀疏图：社交网络里每个人平均好友几百个，但全站用户几千万，用邻接矩阵根本存不下。所以工程上邻接表的出镜率远高于邻接矩阵。
缺点是判断两个顶点是否相连，最坏情况要把整个链表扫一遍，时间复杂度退化为O(度)，不过多数场景下这个代价可以接受。
我自己的习惯是，做题和写Demo时图方便用邻接矩阵，真正做项目、处理大数据量时默认邻接表。没有绝对的好坏，只有合不合适。
2.3 Java实现：从0构建一张邻接表图
光说不练假把式，这里给出一段可以直接跑起来的Java代码，构建一张无向图的邻接表。
import java.util.*; public class Graph { private final int vertices; private final List<List<Integer>> adjList; public Graph(int vertices) { this.vertices = vertices; adjList = new ArrayList<>(vertices); for (int i = 0; i < vertices; i++) { adjList.add(new LinkedList<>()); } } public void addEdge(int u, int v) { adjList.get(u).add(v); adjList.get(v).add(u); // 无向图需要双向添加 } public void printGraph() { for (int i = 0; i < vertices; i++) { System.out.print("顶点 " + i + " 的邻居: "); for (int neighbor : adjList.get(i)) { System.out.print(neighbor + " "); } System.out.println(); } } public static void main(String[] args) { Graph graph = new Graph(5); graph.addEdge(0, 1); graph.addEdge(0, 4); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 3); graph.addEdge(3, 4); graph.printGraph(); } }这段代码跑完，输出的是每个顶点的邻居列表。核心就是addEdge方法里做两次添加，因为无向图的边是双向的。如果你需要构建有向图，去掉第二次添加即可。如果是带权图，把List<List<Integer>>换成List<List<int[]>>，每个int[]里存两个值，一个是目标顶点，一个是权值就行。
等邻接表建好了，你就可以在这张表上做各种遍历和算法了，后面几节都会围绕这张表展开。
3. 图的遍历：BFS和DFS，从原理到代码一次搞懂
遍历是图算法的基础。树有先序中序后序，图更复杂，因为可能存在环路，所以需要一个visited数组（或者集合）记录哪些顶点已经访问过，否则会死循环。图的遍历就两种主流方案：深度优先搜索DFS和广度优先搜索BFS。
3.1 深度优先搜索DFS：一条路走到底，走不动就回头
DFS的思路就像走迷宫，从起点出发，选一条岔路走到底，遇到死胡同就退回到上一个岔路口，再换一条路走。这个“退回去再试”的过程，天然适合用递归实现，因为函数调用栈本身就帮你保存了每一步的状态。
它的应用场景非常多：判断图中是否存在从一个顶点到另一个顶点的路径；计算连通分量的个数；拓扑排序的一种实现方式；迷宫寻路；检测图中是否有环。很多回溯算法，本质都是一棵隐式的图在做DFS。
实现代码不算难，核心套路如下：
void dfs(int v, boolean[] visited, List<List<Integer>> adjList) { visited[v] = true; System.out.print(v + " "); // 访问当前顶点 for (int neighbor : adjList.get(v)) { if (!visited[neighbor]) { dfs(neighbor, visited, adjList); } } }注意一个细节：递归深度等于图的路径长度，如果图特别大或者顶点特别多，递归层数太深可能造成栈溢出。工程上遇到这种情况，可以改成显式使用Stack的迭代版，本质一样，但能更好地控制栈空间。
3.2 广度优先搜索BFS：一层一层往外扩散
BFS的思路更像水波扩散，从起点出发，先把所有一步就能到达的顶点走完，再走两步能到达的，以此类推。由于它按层扩展的特性，天然适合求解“最短路径长度”问题，这里的“最短”指边的数量最少，在无权图中等价于最短路径。
实现BFS必须用队列，这是它的标志性特征。每访问一个顶点，就把它的未访问邻居全部入队，然后从队头取出下一个顶点继续。
void bfs(int start, boolean[] visited, List<List<Integer>> adjList) { Queue<Integer> queue = new LinkedList<>(); visited[start] = true; queue.offer(start); while (!queue.isEmpty()) { int v = queue.poll(); System.out.print(v + " "); for (int neighbor : adjList.get(v)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } }BFS用的地方更多是大家熟悉的场景：社交网络里“你可能认识的人”推荐，就是先找你好友的好友，也就是距离你两层的人；爬虫程序从一个URL出发，不断抓取网页上的链接，本质上也是BFS。如果你后面要学图神经网络，BFS的分层扩散思想也会反复出现。
两种遍历的时间复杂度都是O(V+E)，因为每个顶点最多入队/入栈一次，每条边最多被扫描一次。空间复杂度在最坏情况下，BFS的队列可能同时存O(V)个顶点，DFS的递归栈也最多O(V)层。区别只在于遍历顺序不同，选择哪一种，取决于你关心的是“能否到达”还是“最近几层能到”。
4. 图的应用：最短路径、最小生成树和拓扑排序
图之所以是算法面试和工程应用的重头戏，就是因为围绕它可以延伸出成体系的应用算法。这一节我挑三个最常用、最值得掌握的讲：Dijkstra最短路径、Prim/Kruskal最小生成树、Kahn拓扑排序。每一个都讲清楚“用来解决什么”“核心思路是什么”“代码怎么落地”。
4.1 Dijkstra：带权图的最短路径算法
你打开高德地图规划一条从家到公司的路线，后台跑的核心算法之一就是最短路径算法，而Dijkstra是最经典的单源最短路径算法，也就是“从一个起点到其他所有顶点的最短路径”。
Dijkstra的核心思想是贪心：每一步都从“尚未确定最短路径的顶点”中，选一个当前距离起点最近的顶点，然后把它的邻居松弛一遍。所谓松弛，就是看看“经过当前这个顶点，能不能让邻居到起点的距离更短”，如果能，就更新邻居的距离。
这里有一个前提，Dijkstra要求图中不能有负权边。道理也很简单：贪心策略一旦确定某个顶点的最短距离，就不会再回头更新它，如果后面出现一条负权边把距离拉低，贪心选出来的结果就是错的。遇到负权边，需要用Bellman-Ford算法，不过面试和工作中负权场景很少，Dijkstra完全够用。
为了高效地“取当前距离最小的顶点”，工程实现一般用优先队列（最小堆），Java里就是PriorityQueue。代码如下：
void dijkstra(int start, List<List<int[]>> adjList, int n) { int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] = 0; // int[]{顶点, 距离} PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{start, 0}); while (!pq.isEmpty()) { int[] cur = pq.poll(); int u = cur[0]; int d = cur[1]; if (d > dist[u]) continue; // 过期的记录，跳过 for (int[] edge : adjList.get(u)) { int v = edge[0]; int w = edge[1]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(new int[]{v, dist[v]}); } } } }代码里那个if (d > dist[u]) continue;是优化关键，没有它也不影响正确性，但会白白多处理很多已经过期的队列元素，图大一点性能差别肉眼可见。
4.2 最小生成树：用最少的成本连通所有顶点
普里姆算法和克鲁斯卡尔算法是两种经典的最小生成树算法，目标一致：让n个顶点通过n-1条边连通起来，并且边的总权值最小。现实场景比如：要在n个城市之间铺设通信光缆，已知每两个城市之间的铺设成本，怎么选线路总成本最低；再比如电路板上要连通所有引脚，怎么布线最短。
Prim算法的思路是从一个顶点开始，每次把一个“离当前树最近”的顶点和边收进来，直到所有顶点都进树。Kruskal算法的思路更简单粗暴：先把所有边按权值从小到大排序，然后从最小的边开始，一条一条尝试加入，只要加入后不产生环就保留。判断是否产生环，用的是并查集。
并查集如果你不熟，可以理解成“帮派合并”：每个顶点刚开始是独立的帮派，加入一条边就把两个帮派合并。如果一条边的两个端点已经在同一个帮派里，说明再加入这条边会形成环，必须跳过。
Kruskal的好处是思路直白、代码写起来不容易错，面试时更推荐优先写它。核心代码如下：
class Edge { int u, v, weight; Edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; } } // 使用 Kruskal 算法计算最小生成树总权值 int kruskal(int n, List<Edge> edges) { // 按权值从小到大排序 edges.sort(Comparator.comparingInt(e -> e.weight)); int[] parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; int totalWeight = 0; int edgeCount = 0; for (Edge edge : edges) { int rootU = find(parent, edge.u); int rootV = find(parent, edge.v); if (rootU != rootV) { // 不成环才合并 parent[rootU] = rootV; totalWeight += edge.weight; edgeCount++; if (edgeCount == n - 1) break; } } return totalWeight; } int find(int[] parent, int x) { if (parent[x] != x) { parent[x] = find(parent, parent[x]); // 路径压缩 } return parent[x]; }用的时候把图里所有边放进List，顶点总数传进去，返回的totalWeight就是最小生成树的总权值。路径压缩这行代码别省，它能大幅降低树的深度，让find操作接近O(1)级别。
4.3 拓扑排序：有依赖关系的任务怎么排顺序
拓扑排序处理的是有向无环图，应用场景包括：大学的课程安排（学数据结构前必须先学程序设计基础）、构建系统里编译任务的先后顺序、包管理工具里依赖包的安装顺序。它的输出是一个线性序列，满足“每条边的起点都排在终点之前”。
算法上最常用的是Kahn算法，基于入度来实现：先统计每个顶点的入度，把所有入度为0的顶点入队；然后不断取出一个入度为0的顶点，把它“删除”并输出，同时把所有以它为起点的边去掉，也就是让目标顶点的入度减1；如果某个目标顶点的入度变成0，就继续入队。整个过程循环到最后，如果输出的顶点数不等于总顶点数，说明图里有环，拓扑排序是做不出来的。
List<Integer> topoSort(int n, List<List<Integer>> adjList, int[] inDegree) { Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (inDegree[i] == 0) queue.offer(i); } List<Integer> result = new ArrayList<>(); while (!queue.isEmpty()) { int u = queue.poll(); result.add(u); for (int v : adjList.get(u)) { inDegree[v]--; if (inDegree[v] == 0) queue.offer(v); } } if (result.size() != n) { System.out.println("图中存在环，无法完成拓扑排序"); return new ArrayList<>(); } return result; }这里的关键点在inDegree数组，它需要你在构建图的时候同步统计。每加入一条u到v的有向边，就执行一次inDegree[v]++。有了拓扑排序，你就能很自然地判断一个依赖关系图是否合法，这个判断在构建系统里几乎是刚性需求。
5. 完整实操：构建一张城市交通图并跑通三种算法
前面讲了理论和代码片段，这一节我把它串成一个完整demo，就像做实验一样从头到尾走一遍。假设有6个城市，编号0到5，城市之间的道路和行驶时间如下表：
| 起点 | 终点 | 行驶时间（分钟） |
|---|---|---|
| 0 | 1 | 15 |
| 0 | 2 | 30 |
| 1 | 2 | 10 |
| 1 | 3 | 20 |
| 2 | 3 | 25 |
| 2 | 4 | 35 |
| 3 | 4 | 15 |
| 3 | 5 | 40 |
| 4 | 5 | 20 |
这是一张带权无向图。我们做三件事：构建邻接表，跑一遍从城市0出发的BFS和DFS遍历，再算一遍从城市0到其他所有城市的最短时间。
5.1 构建带权邻接表
带权图的邻接表，每个邻居要同时存两个信息：目标顶点和边的权值。代码用List<List<int[]>>实现，内层int[]的第一个元素是邻居顶点编号，第二个是权值。
List<List<int[]>> buildWeightedGraph(int n, int[][] edges) { List<List<int[]>> adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; int w = edge[2]; adjList.get(u).add(new int[]{v, w}); adjList.get(v).add(new int[]{u, w}); // 无向图反向也加 } return adjList; }5.2 在图上跑BFS和DFS
由于这里主要演示带权图的最短路径，我先跑一个DFS验证图的连通性。从城市0出发，DFS访问顺序是0 → 1 → 2 → 3 → 4 → 5，因为DFS会沿着一条路走到底，1的邻居2、3依次展开，最后从4走到5。如果换BFS，访问顺序是0 → 1 → 2 → 3 → 4 → 5，看起来一样，但中间层的入队顺序不同。两个顺序不一定相同，具体取决于邻居的存储顺序。
这段代码恰好说明了无向图遍历的一个特点：在连通图里，从任意顶点出发都能访问到所有顶点；如果图不连通，就需要在外层循环里再套一层判断，对每个未访问的顶点都做一次遍历，才能统计出连通分量个数。
5.3 用Dijkstra算最短时间
把上面的带权邻接表传给第四节里的dijkstra方法，手动推一遍关键步骤：
- 起点0：dist[1]=15，dist[2]=30，其余为无穷大。
- 从优先队列取出距离最小的顶点1（距离15），松弛它的邻居：城市2经过1只要15+10=25，比原来的30小，更新dist[2]=25；城市3经过1需要15+20=35，dist[3]=35。
- 继续取当前最小，依次确定城市2、3、4、5的最短距离。最终结果是：
| 目标城市 | 最短时间 | 路径 |
|---|---|---|
| 1 | 15分钟 | 0 → 1 |
| 2 | 25分钟 | 0 → 1 → 2 |
| 3 | 35分钟 | 0 → 1 → 3 |
| 4 | 40分钟 | 0 → 1 → 2 → 4 或 0 → 1 → 3 → 4 |
| 5 | 55分钟 | 0 → 1 → 3 → 5 或 0 → 1 → 3 → 4 → 5 |
看到没有，如果直接用0到2的直连路是30分钟，但绕道1只要25分钟，这就是Dijkstra的价值——它比较的不是“直连”，而是“全局最短”。
实际工程里，地图导航还会在Dijkstra基础上做优化，比如加启发式策略，让搜索方向优先指向终点，而不是四面开花。但不管怎么优化，核心思想还是Dijkstra的那一套贪心+松弛框架。
6. 常见问题与排查技巧：那些年我踩过的坑
图相关的题目和项目里，有些错误特别隐蔽，代码跑起来看似正常，结果却不对。这里把我踩过和帮别人排查过的典型问题整理成一个速查表。
| 问题现象 | 根本原因 | 解决办法 |
|---|---|---|
| 遍历时死循环 | 没有维护visited数组，或者visited标记的位置不对 | 入队/入栈前就标记访问，不要等到出队时才标记 |
| 无向图addEdge只加了一条方向 | 构建邻接表时漏掉反向边 | 无向图的addEdge必须双向添加 |
| Dijkstra结果偏大 | 优先队列里塞入了过期的顶点记录，旧记录被重复处理 | 加if (d > dist[u]) continue;跳过过期记录 |
| 带权图用int表示无穷大时相加溢出 | Integer.MAX_VALUE + 权重变成负数 | 先判断dist[u]是否等于无穷大，或改用long |
| 拓扑排序结果为空但图看起来正常 | 统计入度时漏掉了重复边 | 构建图时遇到同一对顶点的多条边，入度要同步累加多次 |
| 认为邻接矩阵一定比邻接表好写 | 顶点多、边少时，矩阵开一个大数组就内存崩溃 | 根据V和E的比例选择，V的平方远大于E就选邻接表 |
除了表里这些，我再补两个经验之谈。
第一个是测试用例一定要包含环和重复边。很多人自测时用的图太“干净”，既没有环也没有重边，算法跑通了就以为万事大吉。实际上环会触发DFS的visited判断，重边会触发最短路径的更新逻辑，你必须在真实数据分布下验证过，才算真正写完。
第二个是复杂度分析一定要算在点子上。比如BFS和DFS是O(V+E)，不是因为代码里有两个循环，而是因为每个顶点、每条边都只访问一次。Kruskal的复杂度是O(E log E)，瓶颈在排序，并查集操作几乎可以忽略。你把复杂度分析说清楚，面试和报告里都会显得专业很多，也能帮你判断自己的代码在大数据量下能不能撑住。
图这块学起来内容确实多，从概念到存储再到算法是一条完整的链路，每层都有对应的坑。但只要像这篇文章一样，先用场景理解概念，再动手写代码，最后在真实用例里调通，你会发现图反而是数据结构里落地价值最高的一章。
