1. 从现实场景理解图这种数据结构把图单独拎出来写是因为它和之前的线性表、树完全不是一个套路。数组、链表、栈、队列这些结构都有明确的“前一个”“后一个”关系树也只允许一个父节点带多个子节点但图没有这么多规矩——任意两个节点之间都可能存在关系一个节点可以和四面八方连出去。学图的时候如果还沿用“顺序”“层次”的思维很容易卡壳。图到底有什么用随便举几个例子城市之间的交通网络每个城市是一个顶点高速公路和航线是边社交应用里的好友关系每个人是顶点互相关注是边电商平台的推荐系统用户和商品是两类顶点一次购买行为就是一条边。这些东西用数组或树都很难建模因为关系是网状的。图就是为了表达这种“多对多”关系而生的数据结构这也是它和前面所有结构最本质的区别。很多人一开始会把图理解成“复杂版的树”这话不算错但必须注意树是一种有层次关系的图而且树里不允许有环图允许有环允许没有根允许顶点之间任意连接。正因为图足够自由处理起来才更需要一套清晰的规则。如果脑子里对图和树的边界没概念后面写遍历、写路径搜索时会经常用树的思维去套图结果就是各种漏点和死循环。1.1 核心术语对齐顶点、边、度正式写代码之前先把术语对齐。图由顶点vertex和边edge组成一条边连接两个顶点。如果边有方向就是有向图比如微博的关注关系A关注B并不代表B关注A如果边没有方向就是无向图比如微信的好友关系A是B的好友B自然也是A的好友。这个“方向”直接影响存储结构的设计后面实现时会看到差别。顶点的度degree指和它相连的边的数量。无向图里度就是邻居个数有向图里还要再分出度和入度出度是它有多少条边指向别人入度是有多少条边指向它。这个指标在做遍历、判断连通性、做拓扑排序的时候经常用到。另外还有几个容易混淆的概念路径、回路、连通图。路径是一串相邻顶点组成的序列回路是起点和终点相同的路径连通图是说任意两个顶点之间都有路径可达。带权图则是在边上附带一个数值比如地图里的距离、网络里的带宽路径规划问题里用的基本都是带权图。这一篇先不展开加权算法但存储结构要有能力容纳权重后面写最短路径时才不用返工。1.2 为什么用Java来学图选Java写图数据结构我自己的理由是偏向工程实践的。Java的面向对象特性让“顶点”“边”可以很直观地建模成类而不是像C语言那样用结构体加指针绕来绕去泛型又能让图支持任意顶点类型String、Integer甚至自定义对象都可以往里放Java标准库里的ArrayList、HashMap、LinkedList都相当成熟拿来当底层容器非常顺手代码写出来又短又不容易出错。当然Java的缺点也很明显对象开销大图特别大的时候内存消耗会比C高不少。但学习阶段我们关心的是逻辑清晰、容易调试Java已经完全够用。如果你平时写别的语言也建议把这里的思路迁移过去图算法思想是通用的语言只是载体。最近几年面试题里用Java写图算法的频率越来越高很多公司问“手写一个图的深度优先遍历”“如何用邻接表存储图”本质上考的就是今天这套东西。2. 图的存储方式邻接矩阵与邻接表确定用什么结构存储图是在写所有图算法之前必须做的决定。两种最常见的方案是邻接矩阵和邻接表它们各有各的适用场景选错了后面会很痛苦。这就像搬家时选纸箱还是行李箱东西少用行李箱方便东西多用纸箱才能装完图也是同理。2.1 邻接矩阵用二维数组表达任意两点关系邻接矩阵的思路非常直接假设图有n个顶点就开一个n乘n的二维数组matrix[i][j]表示顶点i到顶点j是否有边。无向图的矩阵是对称的matrix[i][j]等于matrix[j][i]有向图就不一定对称了。如果是带权图matrix[i][j]存权重不存在的边用一个特殊值比如Integer.MAX_VALUE表示。好处是判断两个顶点是否相连的时间复杂度是O(1)直接查数组下标代码写起来最不容易出错。坏处也很明显空间复杂度是O(n²)哪怕只有几百个顶点顶点数上万后矩阵就是亿级单位的数组内存根本顶不住。所以邻接矩阵更适合稠密图也就是边数接近n²的图或者顶点数量不大的场景。我这里特别提醒一个新手容易忽略的细节用邻接矩阵存带权图时对角线一般设置为0因为顶点到自己没有边而不存在的边要设置成一个不会和合法权重混淆的值。如果用的是Integer.MAX_VALUE后面做加法运算时两个最大值相加会溢出变成负数这是个非常隐蔽的坑写最短路径算法时一定要先对最大值做拦截。2.2 邻接表用列表数组压缩稀疏图空间邻接表是另一种思路。它给每个顶点维护一个列表列表里装的是这个顶点能直接到达的所有邻居。在Java里通常用ArrayListArrayList 或者ArrayListLinkedList 来实现更灵活的做法是用HashMapInteger, List 这样顶点编号不连续时也能处理。邻接表最大的优点是空间复杂度只有O(n e)e是边的数量。一个几千个点但只有几千条边的稀疏图用邻接矩阵要开百万级数组用邻接表只需要存几千个邻居关系省下来的内存非常可观。代价是判断两个顶点是否相邻需要遍历列表复杂度是O(degree)不过大多数算法用邻接表都能跑得不错。邻接表在实现有向图时也很自然对于有向图只需要把边的方向存进对应顶点的列表对于无向图边得在两个端点的列表里各存一次。如果是带权图列表里就不能只存邻居编号了得存一个包含目标顶点和权重的小对象比如用一个内部类Edge。很多教材会在这一步直接引入泛型Pair我建议还是单独建内部类可读性更高。2.3 两种存储方式怎么选我在实际项目里通常遵循一个原则如果边数相对顶点数特别多选邻接矩阵代码简单、判断快反之选邻接表省空间、遍历方便。考试和面试里如果题目没说明默认用邻接表更稳妥因为大部分工程中的图都是稀疏的笔试环境内存有限邻接矩阵写着爽但容易爆内存。还有第三种方案是十字链表和邻接多重表它们在有向图和无向图上有各自的优化但Java里用得少实现也比较复杂这一篇先不深入。等后面讲图的高级应用时再展开。先把邻接矩阵和邻接表写明白图的基本算法已经能跑起来了。为了更直观我整理了一个对比表对比项邻接矩阵邻接表空间复杂度O(n²)O(n e)判断两点是否相邻O(1)O(degree)获取某个顶点的所有邻居O(n)O(degree)适合场景稠密图、顶点数少稀疏图、顶点数多代码复杂度低中边的删除/添加简单简单但要注意双向处理这张表不用背动手写一遍两种实现自然就记住了。我自己的经验是第一次学图的人往往容易在邻接表上栽跟头原因不是概念难而是“现在到底存的是顶点还是下标”没分清。3. 用Java手写一个图的基础骨架理论知识说多了容易飘下面直接上代码。这一篇用两个版本实现同一个无向图先用邻接矩阵再用邻接表都提供添加顶点、添加边、打印图、获取邻居这些基础操作。代码不追求花哨重点是把注释和设计思路讲清楚。3.1 定义顶点和边的数据模型先定义顶点。实际情况里顶点往往有业务含义比如用户名、城市名所以我们用泛型让图可以装任意类型。public class VertexT { private T data; private boolean visited; public Vertex(T data) { this.data data; this.visited false; } public T getData() { return data; } public boolean isVisited() { return visited; } public void setVisited(boolean visited) { this.visited visited; } }这个类看起来简单但visited状态放在顶点上还是放在遍历方法里是有讲究的。很多教材用int[] visited数组按顶点编号记录状态这样更省内存也不会污染顶点对象。我这里把visited放在Vertex里是为了让示例代码更直白但实际生产环境我建议用独立的boolean数组因为图很大时每个顶点多一个字段确实有点浪费而且多线程遍历时顶点状态互相干扰也不好排查。边要不要建模成单独类如果只是表示“是否存在关系”用邻接表里的Integer或邻接矩阵里的boolean就够了没必要单独建类。如果是带权图或者需要记录边的属性建议单独建一个Edge类这样后续扩展最短路径、最小生成树时可以把权重、容量、时间戳之类的字段都塞进去。public class EdgeT { private T from; private T to; private int weight; public Edge(T from, T to, int weight) { this.from from; this.to to; this.weight weight; } public T getFrom() { return from; } public T getTo() { return to; } public int getWeight() { return weight; } }3.2 邻接矩阵版图的代码实现这里用一个固定容量的数组存顶点一个二维数组存边。为了简单假设顶点编号从0到n-1连续构造时传入最大容量。import java.util.ArrayList; import java.util.List; public class MatrixGraphT { private VertexT[] vertices; private int[][] matrix; private int size; SuppressWarnings(unchecked) public MatrixGraph(int capacity) { vertices new Vertex[capacity]; matrix new int[capacity][capacity]; for (int i 0; i capacity; i) { for (int j 0; j capacity; j) { matrix[i][j] 0; } } size 0; } public void addVertex(T data) { if (size vertices.length) { throw new IllegalStateException(图容量已满); } vertices[size] new Vertex(data); } public void addEdge(int from, int to) { checkVertexIndex(from); checkVertexIndex(to); matrix[from][to] 1; matrix[to][from] 1; } public void removeEdge(int from, int to) { matrix[from][to] 0; matrix[to][from] 0; } public ListInteger getNeighbors(int v) { checkVertexIndex(v); ListInteger neighbors new ArrayList(); for (int i 0; i size; i) { if (matrix[v][i] 1) { neighbors.add(i); } } return neighbors; } public void printGraph() { for (int i 0; i size; i) { System.out.print(vertices[i].getData() : ); for (int j 0; j size; j) { if (matrix[i][j] 1) { System.out.print(vertices[j].getData() ); } } System.out.println(); } } private void checkVertexIndex(int index) { if (index 0 || index size) { throw new IllegalArgumentException(顶点下标越界: index); } } }代码里最需要注意的就是addEdge方法。无向图的边是双向的只改一边会留下一个断掉的连接遍历时会漏掉顶点。我见过不止三次这种bug表现就是打印邻居时总有半边缺失。加一个checkVertexIndex校验也很重要否则addEdge里传入一个已经超出size的下标矩阵操作可能不会直接报错而是覆盖到后面还没用到的空间问题隐藏得很深。capacity和size的关系要分清楚。capacity是数组最大能容纳的顶点数size是当前已经加入的顶点数。遍历邻居时只能遍历到size不要把capacity也包括进去否则会访问到还没有初始化的顶点打印出一堆null或者0。这个错误初学者特别容易犯因为构造时二维数组已经按capacity开好了for循环顺手就写了capacity。3.3 邻接表版图的代码实现邻接表我习惯用HashMap加ArrayList的组合这样顶点编号可以不连续后期扩展也很方便。核心结构是MapInteger, List key是顶点编号value是邻居列表。import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class ListGraphT { private MapInteger, VertexT vertexMap; private MapInteger, ListInteger adjList; private int nextIndex; public ListGraph() { vertexMap new HashMap(); adjList new HashMap(); nextIndex 0; } public int addVertex(T data) { int index nextIndex; vertexMap.put(index, new Vertex(data)); adjList.put(index, new ArrayList()); return index; } public void addEdge(int from, int to) { ensureVertexExists(from); ensureVertexExists(to); adjList.get(from).add(to); adjList.get(to).add(from); } public ListInteger getNeighbors(int v) { ensureVertexExists(v); return adjList.get(v); } public void printGraph() { for (Map.EntryInteger, ListInteger entry : adjList.entrySet()) { int v entry.getKey(); System.out.print(vertexMap.get(v).getData() : ); for (int neighbor : entry.getValue()) { System.out.print(vertexMap.get(neighbor).getData() ); } System.out.println(); } } private void ensureVertexExists(int v) { if (!adjList.containsKey(v)) { throw new IllegalArgumentException(顶点不存在: v); } } }这段代码里最容易出问题的地方是ensureVertexExists。如果addEdge传入的下标没有通过addVertex添加过adjList.get(from)会返回null程序直接抛NullPointerException。加上这个检查以后错误信息会清晰很多调试时一眼就能看出是下标问题而不是逻辑问题。另外printGraph里用了HashMap的entrySet。HashMap不保证顺序稳定每次打印邻居的顺序可能会和插入顺序不同这不影响算法正确性但会让调试时对结果产生困惑。如果你希望保持插入顺序可以把vertexMap和adjList都换成LinkedHashMap。这个细节不算core但能省掉不少调试时的疑虑。4. 深度优先遍历与广度优先遍历存储结构搭好之后最基础也最重要的算法就是遍历。遍历的目的是把图中每个顶点按某种规则访问一遍。这里只说两种经典方式深度优先DFS和广度优先BFS它们是后面计算连通分量、检测环、拓扑排序、最短路径等算法的基础。4.1 深度优先一条路走到底再回头深度优先的思路可以用走迷宫来类比从起点出发选一个邻居一直往前走走到没有新邻居的地方就回退一步看看上一个顶点还有没有没走过的邻居重复这个过程直到所有顶点都被访问。递归写法非常简洁public void dfs(int start) { resetVisited(); dfsHelper(start); } private void dfsHelper(int v) { vertexMap.get(v).setVisited(true); System.out.print(vertexMap.get(v).getData() ); for (int neighbor : adjList.get(v)) { if (!vertexMap.get(neighbor).isVisited()) { dfsHelper(neighbor); } } }dfsHelper会沿着邻居一路递归遇到已经访问过的顶点就跳过回到上一层后继续尝试下一个邻居。这里有个很容易忽略的问题如果图不是连通图只从一个起点开始会漏掉其他连通分量。需要遍历整个图时外层要再加一层循环对每个未访问的顶点都调一次dfsHelper。很多初学者在这里漏掉导致只访问到一部分顶点就结束了。非递归版本要手动维护一个栈。Java里可以用ArrayDeque替代Stack因为Stack继承自Vector有锁开销效率不高。非递归DFS需要注意入栈时机一个顶点被访问后立即入栈弹出后再探索它的邻居。如果操作顺序不对遍历结果可能和递归版不一样。我建议理解递归版之后再尝试改成非递归版两个版本对照运行能加深理解。4.2 广度优先一圈一圈往外扩广度优先更像水波扩散从起点开始先把起点的所有邻居都访问完然后再访问邻居的邻居一层一层地往外扩。实现时必须用到队列先进入队列的顶点先扩展才能保证“按层”访问。import java.util.LinkedList; import java.util.Queue; public void bfs(int start) { resetVisited(); QueueInteger queue new LinkedList(); vertexMap.get(start).setVisited(true); System.out.print(vertexMap.get(start).getData() ); queue.offer(start); while (!queue.isEmpty()) { int v queue.poll(); for (int neighbor : adjList.get(v)) { if (!vertexMap.get(neighbor).isVisited()) { vertexMap.get(neighbor).setVisited(true); System.out.print(vertexMap.get(neighbor).getData() ); queue.offer(neighbor); } } } }这里有个容易踩的坑如果不先把邻居标记成visited而是等它出队的时候再标记同一个邻居可能会被多个父节点重复加入队列导致重复访问甚至死循环。正确做法是“入队时立即设置visited”。这个细节在面试里经常被问到也是很多人实际写错的地方。你可以在本子上模拟一遍A的邻居B和CB的邻居也有C如果B入队时没有标记C那么从A扩展到B时C被加到队列之后从A扩展到C时C又被加一次队列里就会出现两个C。另外BFS的最短路径性质值得单独说一句在无权图中BFS第一次访问到某个顶点时的路径一定是最短路径按边数算因为它是按层扩散的。这个结论后面在求最短路径时很有用现在先记住。如果要记录路径可以在入队时额外维护一个parent数组把每个顶点第一次被访问时的前驱节点记下来最后从目标节点倒推回去就是一条最短路径。4.3 遍历结果的解释与验证用一个简单无向图来验证假设有五个顶点A、B、C、D、E边是A-B、A-C、B-D、C-E。从A开始深度优先的一种结果可能是A-B-D-C-E广度优先的结果是A-B-C-D-E。注意DFS结果不唯一具体顺序取决于邻居列表的遍历顺序BFS只要每一层内部邻居顺序固定结果也是固定的。所以写测试用例时不要死记一个答案而是看遍历是否符合规则。我自己的做法是先在纸上画出图的结构然后手动走一遍遍历流程再和程序输出对比。如果发现不一致先检查visited重置了没有再检查队列/栈的进出顺序最后看邻接表里邻居的实际排列顺序。只要这三个地方没问题遍历结果基本不会错。这两个遍历的时间复杂度其实很好算DFS和BFS在邻接表上都是O(n e)因为每个顶点访问一次每条边在无向图里会被看到两次在有向图里被看到一次在邻接矩阵上都是O(n²)因为每次都要扫描一整行判断邻居。写成大O表示法时邻接表明显更适合稀疏图。5. 常见问题与排查技巧实录写图相关代码尤其是第一次上手的时候有几个问题出现频率特别高。我把它们整理出来碰到类似的情况可以对照排查。5.1 数组越界与下标管理邻接矩阵版里最容易出现的是ArrayIndexOutOfBoundsException。原因通常是addVertex时超过了capacity或者addEdge时传入了没有分配过的顶点下标。解决方法是所有涉及下标的操作都先检查范围就像上面代码里的checkVertexIndex。for循环里尤其要注意是用size还是capacity我把这俩搞混过不止一次打印时多打了一堆0排查了很久才发现是遍历到了空位。调试技巧在addEdge和getNeighbors的入口处打印出入参下标再配合当前size基本能定位是哪个调用越界。如果用的是HashMap版邻接表则要检查key是否存在而不是检查数组边界。5.2 重复边与自环无向图里如果添加边时忘了双向写入就会造成单向连接这是“半边缺失”问题常见于addEdge只写了matrix[from][to]1而漏了matrix[to][from]1。另外如果from和to相等就会产生自环即顶点和自己相连。有些算法对自环很敏感BFS会多一次无意义的访问DFS如果没控制好visited可能还会死循环。实际项目中是否允许自环和重复边取决于业务定义。比如社交图里一个人不能自己关注自己那么添加边前要加过滤但如果是知识图谱某些实体之间可能确实存在多条含义不同的关系这时重复边反而要保留。存储结构最好能灵活处理可以在addEdge里加一个if (from to)的判断再决定是抛出异常还是忽略。5.3 遍历顺序不一样是bug吗很多朋友会发现自己的DFS输出和网上示例不一样第一反应是代码写错了。其实DFS的结果本来就不唯一只要每个顶点只被访问一次并且访问路径遵循“能深入就深入”的原则顺序不同是正常的。真正需要怀疑代码的情况是同一个顶点被打印了两次或者有些顶点没被打印。出现重复访问检查visited是不是在入栈/入队时就设置了出现漏访问检查外层循环是否覆盖了非连通分量。还有一个和HashMap有关的小坑如果邻接表用HashMap存储顶点信息Java的HashMap不保证遍历顺序稳定打印图时邻居顺序可能和插入顺序不同。这不会影响算法正确性但会让你觉得输出“很奇怪”。如果想稳定输出把vertexMap换成LinkedHashMap就行。5.4 动手练习建议代码光看不练是学不会的。我建议你把这几个任务都亲手做一遍第一用邻接表和邻接矩阵分别实现同一个三顶点图打印出所有邻居第二在纸上画出A-B、A-C、B-C这样的三角形图跑一遍DFS和BFS对比是否和手工推导一致第三给图增加一个removeVertex方法删除顶点时要把所有相邻边也清掉。这个操作在邻接矩阵里要删一行一列在邻接表里要遍历所有列表上面代码没实现建议自己补上。补removeVertex的时候会碰到一个有意思的问题如果使用Map存储删除一个key后原来的顶点编号会留下空洞后续遍历要小心而用连续数组删除顶点后要不要把后面的顶点往前挪也是设计决策。这些东西没有标准答案但动手思考一遍之后你对图存储结构的理解会深很多。6. 图还能做些什么从基础到进阶这一篇能跑通存储和遍历之后已经具备了继续深入图算法的底子。后续至少要接触几个方向一个是最短路径问题典型算法有Dijkstra和Bellman-Ford一个是最小生成树问题典型算法有Prim和Kruskal还有一个是拓扑排序专门处理有向无环图常用于项目依赖关系的构建。这些算法里有相当一部分会复用今天实现的邻接表结构和BFS/DFS思路。我个人的建议是不要急着把所有算法都刷一遍先把图的两种存储结构写到能默写的程度再把DFS和BFS的递归版、非递归版都跑一遍。图这种结构靠看是看不熟的你在纸上画一个随机的十顶点图然后亲手写代码遍历它踩过几个重复访问和漏访问的坑之后才算真正入门。后面聊最短路径和最小生成树的时候我会默认你今天这些基础已经过关了。