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(VE)V是顶点数E是边数。边的数量远少于顶点平方的稀疏图用邻接表能省下大把内存。实际开发里绝大多数场景都是稀疏图社交网络里每个人平均好友几百个但全站用户几千万用邻接矩阵根本存不下。所以工程上邻接表的出镜率远高于邻接矩阵。缺点是判断两个顶点是否相连最坏情况要把整个链表扫一遍时间复杂度退化为O(度)不过多数场景下这个代价可以接受。我自己的习惯是做题和写Demo时图方便用邻接矩阵真正做项目、处理大数据量时默认邻接表。没有绝对的好坏只有合不合适。2.3 Java实现从0构建一张邻接表图光说不练假把式这里给出一段可以直接跑起来的Java代码构建一张无向图的邻接表。import java.util.*; public class Graph { private final int vertices; private final ListListInteger 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方法里做两次添加因为无向图的边是双向的。如果你需要构建有向图去掉第二次添加即可。如果是带权图把ListListInteger换成ListListint[]每个int[]里存两个值一个是目标顶点一个是权值就行。等邻接表建好了你就可以在这张表上做各种遍历和算法了后面几节都会围绕这张表展开。3. 图的遍历BFS和DFS从原理到代码一次搞懂遍历是图算法的基础。树有先序中序后序图更复杂因为可能存在环路所以需要一个visited数组或者集合记录哪些顶点已经访问过否则会死循环。图的遍历就两种主流方案深度优先搜索DFS和广度优先搜索BFS。3.1 深度优先搜索DFS一条路走到底走不动就回头DFS的思路就像走迷宫从起点出发选一条岔路走到底遇到死胡同就退回到上一个岔路口再换一条路走。这个“退回去再试”的过程天然适合用递归实现因为函数调用栈本身就帮你保存了每一步的状态。它的应用场景非常多判断图中是否存在从一个顶点到另一个顶点的路径计算连通分量的个数拓扑排序的一种实现方式迷宫寻路检测图中是否有环。很多回溯算法本质都是一棵隐式的图在做DFS。实现代码不算难核心套路如下void dfs(int v, boolean[] visited, ListListInteger 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, ListListInteger adjList) { QueueInteger 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(VE)因为每个顶点最多入队/入栈一次每条边最多被扫描一次。空间复杂度在最坏情况下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, ListListint[] adjList, int n) { int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] 0; // int[]{顶点, 距离} PriorityQueueint[] 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, ListEdge 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就继续入队。整个过程循环到最后如果输出的顶点数不等于总顶点数说明图里有环拓扑排序是做不出来的。ListInteger topoSort(int n, ListListInteger adjList, int[] inDegree) { QueueInteger queue new LinkedList(); for (int i 0; i n; i) { if (inDegree[i] 0) queue.offer(i); } ListInteger 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城市之间的道路和行驶时间如下表起点终点行驶时间分钟011502301210132023252435341535404520这是一张带权无向图。我们做三件事构建邻接表跑一遍从城市0出发的BFS和DFS遍历再算一遍从城市0到其他所有城市的最短时间。5.1 构建带权邻接表带权图的邻接表每个邻居要同时存两个信息目标顶点和边的权值。代码用ListListint[]实现内层int[]的第一个元素是邻居顶点编号第二个是权值。ListListint[] buildWeightedGraph(int n, int[][] edges) { ListListint[] 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方法手动推一遍关键步骤起点0dist[1]15dist[2]30其余为无穷大。从优先队列取出距离最小的顶点1距离15松弛它的邻居城市2经过1只要151025比原来的30小更新dist[2]25城市3经过1需要152035dist[3]35。继续取当前最小依次确定城市2、3、4、5的最短距离。最终结果是目标城市最短时间路径115分钟0 → 1225分钟0 → 1 → 2335分钟0 → 1 → 3440分钟0 → 1 → 2 → 4 或 0 → 1 → 3 → 4555分钟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(VE)不是因为代码里有两个循环而是因为每个顶点、每条边都只访问一次。Kruskal的复杂度是O(E log E)瓶颈在排序并查集操作几乎可以忽略。你把复杂度分析说清楚面试和报告里都会显得专业很多也能帮你判断自己的代码在大数据量下能不能撑住。图这块学起来内容确实多从概念到存储再到算法是一条完整的链路每层都有对应的坑。但只要像这篇文章一样先用场景理解概念再动手写代码最后在真实用例里调通你会发现图反而是数据结构里落地价值最高的一章。