企业官网建设流程全解析

开头：为什么要单独聊“图”

在工作里摸爬滚打几年后，你会发现很多看似复杂的业务场景，最后都指向同一个数据结构——图。社交网络里的好友关系、地图导航的最短路径、电商推荐里的用户与商品关联、甚至编译器里的依赖分析，底层全都在用图来建模。可以说，树解决的是层次关系，链表解决的是线性关系，而图解决的才是真正的关系网络。

这篇是“java数据结构---图”系列的第一篇，我打算把图的基本概念、两种核心存储结构、以及最常用的两种遍历方式一次性讲透。内容定位是入门到进阶的过渡段，适合已经掌握数组、链表、栈、队列和树，正准备啃下图这块硬骨头的同学。我会用 Java 代码一步步搭建一个可运行的图结构，配合踩坑心得，让你明白“图为什么这么设计”而不是单纯背代码。

1. 图的结构本质与设计思路

1.1 图到底是什么，它和树的区别在哪

先从最朴素的角度理解图。你微信里有 500 个好友，你认识 A，A 认识 B，B 又认识 C，那么从你到 C 实际上有一条“路径”。但在这条路径之外，C 可能还直接认识你的另一个好友 D。这种关系用树没法表达，因为树的节点之间只能是父子关系，一个节点只有一个父节点。图打破了这个限制，任意两个节点之间都可以有关系。

形式化的定义很简单：图 G = (V, E)，V 是顶点集合，E 是边集合。顶点就是一个个实体，边就是实体之间的关系。边还可以有方向，如果 A 关注了 B，不代表 B 也关注了 A，这种就是有向图。如果边不带方向，就叫无向图，好比微信好友关系，你加了对方，对方也就成了你的好友。树其实是一种特殊的图，它是无环连通的无向图，也就是说图的覆盖面比树大得多。

有一个生活化类比非常贴切：图就像你所在城市的公交线路图，每个站点是顶点，线路是边。树像是公司组织结构图，从 CEO 往下只能一层层汇报。这个区别决定了后面选择存储结构、遍历算法时思考方式完全不一样。

1.2 图解决什么场景问题，为什么值得专门学

图的核心价值在于建模“多对多”关系。举几个实际的场景你就明白了：

• 社交推荐：你和某人有共同好友，系统算出你们之间的距离为 2，于是向你推荐他。这里求的就是两个顶点之间的最短路径。
• 地图导航：城市道路是图的边，十字路口是图的顶点，从 A 点到 B 点找耗时最短路径，本质上是最短路径算法，比如 Dijkstra 或者 A*。
• 任务调度：项目里有些任务依赖前置任务完成，用有向图表示依赖关系，再通过拓扑排序决定执行顺序。
• 网络连通性：判断两个路由器之间是否连通，等价于在图里做一次遍历看能否访问到目标顶点。

这些场景共同点非常明显：数据之间存在复杂的关联，而且关联的密集程度是不均匀的。用数组存线性关系、用树存层次关系都不合适，图是最自然的选择。

1.3 学习图之前需要哪些前置知识

图的知识点非常依赖前面几个数据结构的基础，我建议你在动手写代码之前先自查一下：

• 递归：图的深度优先遍历用递归实现最简洁，递归终止条件就是回溯的关键。如果你递归还不熟，先补一补阶乘和斐波那契的递归写法。
• 队列和栈：广度优先遍历是队列的经典应用，比如树的层序遍历。栈可以用于实现非递归版的深度优先遍历。
• 哈希表/数组：存储顶点和边的时候，无论是邻接表还是邻接矩阵，都离不开数组和哈希映射，需要理解用“键”找“值”这个思路。

如果你这些部分都有点模糊，建议先花一两个小时复习。不然直接啃图的代码，很容易被“递归 + 标记数组 + 邻接表”三座大山压懵。

2. 图的存储结构：邻接矩阵 vs 邻接表

2.1 邻接矩阵的实现原理和 Java 代码

邻接矩阵的思路非常简单粗暴：用二维数组 matrix[i][j] 表示顶点 i 和顶点 j 之间是否存在边。无向图的矩阵是对称的，有向图不需要对称。如果边带权重，可以把布尔值换成数值，0 表示没有直接边，非 0 表示权重。

我写一个最简版本给你参考：

public class GraphMatrix { private int[] vertices; // 顶点数组，下标对应顶点编号 private int[][] adjMatrix; // 邻接矩阵 private int vertexCount; // 顶点数量 private boolean directed; // 是否是有向图 public GraphMatrix(int size, boolean directed) { this.vertexCount = size; this.directed = directed; vertices = new int[size]; adjMatrix = new int[size][size]; for (int i = 0; i < size; i++) { vertices[i] = i; } } public void addEdge(int from, int to) { adjMatrix[from][to] = 1; if (!directed) { adjMatrix[to][from] = 1; } } public void printMatrix() { for (int i = 0; i < vertexCount; i++) { for (int j = 0; j < vertexCount; j++) { System.out.print(adjMatrix[i][j] + " "); } System.out.println(); } } }

这种实现你能非常直观地看到“数据是怎么存的”。二维数组里的每一个格子，代表了一条可能存在的边。判断 i 和 j 是否相连，只需要 O(1) 的时间，这是它的最大优点。

但问题也随之而来。假设你有 10000 个顶点，邻接矩阵需要 10000 * 10000 个 int，也就是大约 4 亿字节，约等于 381 MB。如果图只有 20000 条边（已经很稀疏了），绝大多数格子存的是 0，纯属浪费空间。所以邻接矩阵更适合稠密图，或者顶点数量小、需要频繁判断边是否存在的场景，比如 Floyd 多源最短路径算法。

2.2 邻接表的实现原理和 Java 代码

邻接表的思路是“只存实际存在的边”。每个顶点对应一个链表，链表中保存的是与这个顶点直接相连的邻居。这样可以大幅节省稀疏图的存储空间。Java 里用 ArrayList 来实现这个链表最方便。

import java.util.ArrayList; import java.util.List; public class GraphAdjList { private List<List<Integer>> adjList; public GraphAdjList(int vertexCount) { adjList = new ArrayList<>(vertexCount); for (int i = 0; i < vertexCount; i++) { adjList.add(new ArrayList<>()); } } public void addEdge(int from, int to) { adjList.get(from).add(to); // 无向图还需要反向添加 // adjList.get(to).add(from); } public List<Integer> getNeighbors(int vertex) { return adjList.get(vertex); } public int size() { return adjList.size(); } }

这个版本只用了三个核心方法：建图、加边、取邻居。遍历某个顶点的所有邻居，时间复杂度是 O(度)，也就是和这个顶点的实际关系数成正比。对于千万级顶点、亿级边的社交网络图，邻接表是唯一现实的选择。

不过邻接表也有代价，判断“顶点 i 和 j 是否有边”需要遍历 i 的邻居列表，最坏情况是 O(度)。如果这个操作非常频繁，就不如邻接矩阵了。还有一点，从列表里删除一条边也比较麻烦，需要遍历查找再删除，后续要讲图的高级算法时再权衡。

2.3 两种存储结构的选择标准：场景决定一切

邻接矩阵和邻接表的选择不是技术高低之争，而是适用场景之争。我整理了一张对照表，放在这里方便你直接参考：

在实际项目中，绝大多数图都是稀疏的。一个社交网络用户平均好友几百个，但顶点是十亿级别，邻接矩阵根本不可能用。所以我个人更推荐你优先掌握邻接表的思维，面试时如果问到“你怎么存图”，先分析图的稀疏程度再决定方案，这个回答本身就加分。

2.4 带权边的扩展设计

实际场景里，光知道“A 和 B 有没有关系”往往不够，还要知道关系的“强度”。比如地图导航里的距离、电商推荐里的相似度分数。这时候需要把存储结构升级为带权图。

带权邻接表最常见的做法是把链表里的元素从一个 int 换成一个内部类：

class Edge { int to; int weight; Edge(int to, int weight) { this.to = to; this.weight = weight; } }

这样 addEdge 就变成了：

public void addWeightedEdge(int from, int to, int weight) { adjList.get(from).add(new Edge(to, weight)); }

带权邻接矩阵则是在 matrix[i][j] 的位置存放权重值，用 0 或者一个无穷大的特殊值表示“无边”。这里有一个小坑：如果权重本身可能为 0，就不能用 0 表示无边，需要定义一个很大的值，比如 Integer.MAX_VALUE / 2，防止后续做加法时溢出。

3. 从零搭建一个可复用的 Java 图类

3.1 需求分析与类设计思路

我先明确一下目标：设计一个尽量通用的图类，既能表示有向图也能表示无向图，顶点用泛型支持任意类型，底层用邻接表。这个类要足够简单，让初学者看得懂，同时结构上又能直接扩展出后续文章要讲的 BFS、DFS、拓扑排序等算法。

我建议不要在一个类里塞太多东西。图的存储结构是一层，遍历算法可以放在单独的工具类里。这样职责清晰，后续加新算法不需要频繁改动图的存储代码。下面的实现复用了前面 GraphAdjList 的思路，但把顶点数据类型泛型化了，并且用 HashMap 把顶点值映射到数组下标。

3.2 完整的图类代码实现

import java.util.*; public class Graph<T> { private Map<T, Integer> vertexIndexMap; // 顶点 -> 数组下标 private List<T> vertexList; // 数组下标 -> 顶点 private List<List<Integer>> adjList; // 邻接表 private boolean directed; public Graph(boolean directed) { this.directed = directed; vertexIndexMap = new HashMap<>(); vertexList = new ArrayList<>(); adjList = new ArrayList<>(); } public void addVertex(T vertex) { if (!vertexIndexMap.containsKey(vertex)) { vertexIndexMap.put(vertex, vertexList.size()); vertexList.add(vertex); adjList.add(new ArrayList<>()); } } public void addEdge(T from, T to) { addVertex(from); addVertex(to); int fromIdx = vertexIndexMap.get(from); int toIdx = vertexIndexMap.get(to); adjList.get(fromIdx).add(toIdx); if (!directed) { adjList.get(toIdx).add(fromIdx); } } public List<T> getNeighbors(T vertex) { Integer idx = vertexIndexMap.get(vertex); if (idx == null) { return Collections.emptyList(); } List<Integer> neighborIdxList = adjList.get(idx); List<T> neighbors = new ArrayList<>(neighborIdxList.size()); for (Integer neighborIdx : neighborIdxList) { neighbors.add(vertexList.get(neighborIdx)); } return neighbors; } public int size() { return vertexList.size(); } public List<T> getVertices() { return new ArrayList<>(vertexList); } }

这个类有四个关键点我逐一解释：

• vertexIndexMap 和 vertexList 互为反向索引。为什么两套结构都要？因为图算法里经常需要根据顶点拿到下标（比如标记 visited 数组），也经常需要根据下标拿到顶点的值（比如遍历时打印顶点），只保留一套会非常痛苦。
• addVertex 方法做了去重。如果顶点已经存在，直接忽略。这在后面批量添加边时非常省心，不用关心顶点是否已存在。
• 邻接表里存的是下标而不是顶点的值。这是性能考量。存下标，数组访问是 O(1)；存对象的话，每次都要做 equals 比较，而且对象可能很大，浪费内存。获取邻居时再通过 vertexList 映射回顶点值对外输出。
• directed 标志控制是否添加反向边。这样同一个类既能表示有向图，也能表示无向图，用法上只是构造参数不同。

3.3 用一个实际例子验证图类

我模拟一个简单的社交推荐场景来测试这个图类：用户 A 认识 B 和 C，B 又认识 D，C 也认识 D。构建代码：

public class GraphDemo { public static void main(String[] args) { Graph<String> socialGraph = new Graph<>(false); socialGraph.addEdge("A", "B"); socialGraph.addEdge("A", "C"); socialGraph.addEdge("B", "D"); socialGraph.addEdge("C", "D"); socialGraph.addEdge("D", "E"); System.out.println("顶点数量: " + socialGraph.size()); for (String vertex : socialGraph.getVertices()) { System.out.println(vertex + " 的邻居: " + socialGraph.getNeighbors(vertex)); } } }

输出结果：

顶点数量: 5 A 的邻居: [B, C] B 的邻居: [A, D] C 的邻居: [A, D] D 的邻居: [B, C, E] E 的邻居: [D]

从输出能直观看到无向图“边是双向的”这一特性。每条 addEdge 都自动补了反向边，所以 A 添加 B 之后，B 的邻居列表里也自动出现了 A。

3.4 图的整体设计与算法分层

图这个数据结构有个特点：存储结构相对固定，但算法复杂度跨度极大。所以我的建议是，把存储结构和算法分开设计。你完全可以创建一个单独的算法类，接收 Graph 作为参数：

public class GraphAlgorithms { public static <T> List<T> bfs(Graph<T> graph, T start) { // 这里调用 graph.getNeighbors() 就能完成遍历，无需关心内部存储 } }

这么设计的好处非常明显：后续如果要把邻接表换成邻接矩阵，只需要保证 Graph 类对外接口不变，算法代码一行都不用改。这也是开发中“面向接口编程”思想的一个小落地。

4. 图的遍历：从一点出发走遍全图

4.1 为什么遍历图和遍历树不一样

树的遍历你肯定已经很熟了，但图遍历多了一个“麻烦”——回路。树中从一个节点往下走不会回到起点，因为树没有环。图的边可以形成环，比如 A -> B -> C -> A，如果你按照树的递归思路去遍历，就会陷入无限循环。

解决办法是引入一个visited 数组（标记数组）。每访问一个顶点，先检查是否访问过，访问过就直接跳过。这个思路极其简单，但它是所有图算法的基础。BFS、DFS、拓扑排序、最短路径、连通分量判断，全都要靠它。

4.2 广度优先遍历 BFS：一层一层往外扩散

BFS 的思路就像你站在湖边往水里扔一块石头，水波一圈一圈往外扩散。先访问距离起点为 1 的所有顶点，再访问距离为 2 的所有顶点。实现时用队列来辅助，把当前顶点的所有未访问邻居加入队列，先进先出保证先入队的先被处理。

import java.util.*; public class GraphTraversal { public static <T> List<T> bfs(Graph<T> graph, T start) { List<T> result = new ArrayList<>(); if (graph == null || !graph.getVertices().contains(start)) { return result; } Queue<T> queue = new LinkedList<>(); Set<T> visited = new HashSet<>(); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { T current = queue.poll(); result.add(current); for (T neighbor : graph.getNeighbors(current)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } return result; } }

这里关键的一行是visited.add(neighbor)。我见过很多新手把标记 visit 的时机放在从队列取出之后，也就是先进入队列，等出队时才标记。这个做法在图上会导致同一个节点被重复加入队列，极端情况下 BFS 会退化得很严重。正确做法是入队时立即标记，这样每个顶点只会被入队一次。

4.3 深度优先遍历 DFS：一条路走到黑再回头

DFS 的思路不一样，它更像走迷宫：从起点出发，一直沿着某条支路往下走，走到死胡同再退回来换一条路。实现可以用递归，也可以用栈。递归写法比较简洁，但要注意深度很大的图可能导致栈溢出，这个我后面会专门讲。

public static <T> void dfsRecursive(Graph<T> graph, T vertex, Set<T> visited, List<T> result) { if (visited.contains(vertex)) { return; } visited.add(vertex); result.add(vertex); for (T neighbor : graph.getNeighbors(vertex)) { dfsRecursive(graph, neighbor, visited, result); } } public static <T> List<T> dfs(Graph<T> graph, T start) { List<T> result = new ArrayList<>(); Set<T> visited = new HashSet<>(); dfsRecursive(graph, start, visited, result); return result; }

递归版本的思路非常清爽：访问当前顶点，然后把每个没访问过的邻居扔进递归。你可以想象成递归栈在帮你维护“下一步去哪”的状态。对于不习惯递归的读者，我再用栈实现一遍非递归版：

public static <T> List<T> dfsIterative(Graph<T> graph, T start) { List<T> result = new ArrayList<>(); if (graph == null || !graph.getVertices().contains(start)) { return result; } Set<T> visited = new HashSet<>(); Deque<T> stack = new ArrayDeque<>(); stack.push(start); while (!stack.isEmpty()) { T current = stack.pop(); if (visited.contains(current)) { continue; } visited.add(current); result.add(current); List<T> neighbors = graph.getNeighbors(current); // 倒序入栈，保证遍历顺序和递归版本一致 for (int i = neighbors.size() - 1; i >= 0; i--) { T neighbor = neighbors.get(i); if (!visited.contains(neighbor)) { stack.push(neighbor); } } } return result; }

用栈模拟有一个微妙的细节：因为栈是后进先出，如果直接把邻居按顺序压入栈，第一个邻居会被压在底下，最后才被访问。为了让非递归遍历的顺序和递归版本保持一致，需要把邻居列表倒序入栈。如果你不管遍历顺序的细节，只关心所有节点是否被访问到，不倒序也没关系。但面试或者做题时如果要求输出顺序和递归版一致，这就是一个非常隐蔽的坑。

4.4 BFS 和 DFS 的适用场景选择

BFS 和 DFS 没有绝对的好坏，核心看需求。

BFS 的优点是最先找到的路径一定是步数最短的，所以“最少转机次数”“最短路径层数”这类问题首选 BFS。缺点是空间消耗大，因为要维护队列，队列里最多可能存一整层的节点。DFS 的优点是实现简单，空间上递归栈的深度通常比 BFS 的队列深度小，适合处理“是否存在路径”“连通性判断”“拓扑排序”这类问题。缺点是不保证最短路径，而且递归有栈溢出风险。

我把两者的特点整理成了表格：

实际写业务代码时，我通常先用 BFS 解决“能不能”、“最近多远”这类问题，再用 DFS 解决“有几条路径”、“怎么排序”这类问题。

4.5 全图遍历与连通分量的一个补充点

前面实现的 BFS 和 DFS 都是从某一个起点出发的。但图可能是非连通图，也就是说从任何一个顶点出发都无法访问到所有顶点。要遍历整张图，需要在外层再套一个循环：

public static <T> List<List<T>> bfsAll(Graph<T> graph) { List<List<T>> components = new ArrayList<>(); Set<T> visited = new HashSet<>(); for (T vertex : graph.getVertices()) { if (!visited.contains(vertex)) { List<T> component = new ArrayList<>(); Queue<T> queue = new LinkedList<>(); queue.offer(vertex); visited.add(vertex); while (!queue.isEmpty()) { T current = queue.poll(); component.add(current); for (T neighbor : graph.getNeighbors(current)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } components.add(component); } } return components; }

这种外层循环套遍历的方法，能非常自然地求出图的连通分量。每一轮内层遍历跑完，就找到了一个连通分量。这个思路后续做“朋友圈数量”、“岛屿数量”这类经典算法题时会反复出现。

5. 实操中的常见问题与排查技巧实录

5.1 问题一：未重置 visited 导致二次遍历结果错误

这是我见过最多人踩的坑。你第一次调用bfs(graph, "A")没问题，第二次调用bfs(graph, "B")，如果 visited 集合是成员变量而不是方法内局部变量，第二次遍历时顶点都被标记成“已访问”了，结果直接为空或者少了很多节点。

排查方法很简单：确认 visited 每次调用方法时都是新建的。如果你封装了一个图类，把 visited 作为成员变量，那就要在每次算法调用入口处调用visited.clear()。我个人的习惯是永远把 visited 作为方法内的局部变量，用完即销毁，这样不会产生状态残留。

5.2 问题二：大规模图的递归 DFS 爆栈

递归写法虽然好看，但 JVM 的调用栈深度是有限制的。默认情况下 JVM 栈深度通常在几千到上万的量级，一亿个顶点的图如果深度遍历到一个很长的分支，直接抛StackOverflowError。

我的实际建议是：

• 图规模小（几千个顶点以内），递归 DFS 完全够用。
• 图规模大，或者明确知道路径深度可能超过一万，就直接用显式栈 + 迭代版本。
• 如果必须用递归，可以调大 JVM 的栈大小，启动参数加-Xss10m，但这是治标不治本，偶尔能帮你跑通测试，生产环境该换迭代还是要换。

5.3 问题三：自环和平行边导致遍历重复

自环指的是 A 到 A 的边。addEdge("A", "A")之后，A 的邻居列表里包含了 A 自己。如果用 BFS，处理到 A 的邻居 A 时，发现 A 已经在 visited 里了，会直接跳过，问题不大。但如果你的 visited 标记时机写错了（出队时才标记），自环会导致 A 被重复加入队列。

平行边指的是 A 到 B 出现了多条边。比如在无向图里调用两次addEdge("A", "B")，A 的邻居列表里会有两个 B，B 的邻居列表里也有两个 A。BFS 时 B 第一次遇到就入队并被标记，第二次再遇到会被 visited 挡住，不会出错，但会消耗不必要的循环时间。如果对这部分性能敏感，可以在 addEdge 里加一个是否已存在边的判断。

5.4 问题四：顶点对象没有正确实现 equals 和 hashCode

如果你用自定义对象作为图的顶点（比如 User 对象），visited 的判断依赖对象的equals()和hashCode()。这两个方法没实现或者实现得不对，HashSet 就会把两个内容相同的对象当作不同顶点，直接导致遍历时明明访问过了，还会再次访问，甚至死循环。

排查方法很直接：在顶点类里重写equals和hashCode。如果用的是 Java 17 及以上，可以用record定义顶点类型，编译器自动生成这两个方法，省心省力。如果是老版本，IDEA 里一键生成也不是难事。

5.5 问题五：稀疏图强行用邻接矩阵把内存撑爆

曾经接手过一个模拟项目，顶点数量 5 万，边数量 20 万，第一版用邻接矩阵存储，程序一启动就报内存溢出。后来把存储结构换成邻接表，同样的数据只用了不到原本十分之一的内存。这提醒我：写代码前先估算一下数据规模。5 万顶点用邻接矩阵需要 25 亿个 int，约 10 GB，任何 JVM 默认设置都扛不住。而邻接表存 20 万条边，每个边对象几十字节，总内存轻松控制在 50 MB 以内。

5.6 一些调试和测试的实用技巧

最后分享几个我平时调试图算法的经验：

• 手动画小图跑一遍：新建一个只有 5 到 7 个顶点的图，打印出邻接表，手动模拟一遍 BFS/DFS，再和代码输出对比。这个过程看起来笨重，但排查逻辑错误特别有效。
• 给图类加一个 print 方法：开发阶段把邻接表的内容打印出来，方便随时确认数据是否按预期构建。生产环境上线前再删掉或者降低日志级别。
• 先测试边界情况：空图、只有一个顶点、两个顶点一条边、完全图，这些边界用例能帮你提前发现NullPointerException和IndexOutOfBoundsException。
• 用总数校验结果：遍历完一张连通图，结果列表的长度应该等于顶点总数。如果少了，说明有顶点没被访问到，大概率是 visited 逻辑写错了。

尾声：关于图的一点个人体会

我在第一次学图的时候，也觉得概念抽象、代码绕。后来发现关键是先接受“顺序遍历”这个思维转变：树遍历是天然有方向的，图遍历必须依赖标记数组来控制方向。一旦把这个坎迈过去，后面学习最短路径、最小生成树、拓扑排序时，都是在这个基础框架里加一些优化策略。比如 Dijkstra 就是 BFS 加权重优先级队列，Prim 也类似，拓扑排序是 DFS 加上一个结果栈。

这一篇把图的存储和遍历打扎实了，下一篇我准备接着讲拓扑排序和最短路径这两个高频实战算法。建议你拿到代码后不要只读，新建一个测试类，造个 10 个顶点左右的图，把 BFS 和 DFS 的每一步输出打出来对照着看。数据结构和算法这东西，看十遍不如亲手跑一遍。