图的遍历（DFS+BFS）

更加完整详细内容可查看【免费版Java学习笔记】和【免费版Java面试题】

免费版Java学习笔记（28w字）链接：https://www.yuque.com/aoyouaoyou/sgcqr8
免费版Java面试题（20w字）链接：https://www.yuque.com/aoyouaoyou/wh3hto
完整版Java学习笔记200w字，附有代码实现，图解清楚，仅需9.9
完整版Java面试题，150w字，高频面试题，内容详细，仅需9.9
完整版链接：
https://www.xiaohongshu.com/user/profile/63c2d512000000002601232c
祝您新的一年事事马到成功，身体健康，阖家幸福，大展宏图！

一、图的遍历介绍

1.1 遍历的定义与要求

图的遍历是指从图中任意指定顶点（初始点）出发，按照特定搜索策略沿着边访问所有顶点且每个顶点仅访问一次的过程，遍历得到的顶点序列称为遍历序列。
要求：全访问、不重复——这是因为图存在环和多对多连接，相比二叉树（无环、一对多），遍历需增加访问标记避免重复访问，是图遍历的关键要点。

1.2 两种搜索策略

根据访问顶点的顺序不同，图的遍历分为深度优先搜索（DFS）和广度优先搜索（BFS），二者是图论中最基础、应用最广泛的算法，分别基于栈和队列实现，适配不同的业务场景：

• DFS：深度优先，“一条路走到黑”，适合判断连通性（是否存在路径）；
• BFS：广度优先，“地毯式层层推进”，适合求解最短路径（无权图）。

1.3 与二叉树遍历的关联与差异

二叉树的前/中/后序遍历本质是特殊的图遍历（二叉树是无环的连通图），但图的遍历更复杂，差异如下：

二、深度优先搜索（DFS，Depth First Search）

2.1 思想

DFS的是“深度优先，回溯探索”，类似走迷宫：从起点出发，选择一个方向一直往前走，直到走到“死胡同”（当前顶点无未访问的邻接顶点），再回溯到上一个顶点，尝试其他未走的方向，直到遍历所有顶点。
简单总结：先深后广，遇阻回溯。

2.2 实现依赖

DFS的实现依赖栈（Stack）（后进先出LIFO），有两种实现方式：

1. 递归实现：利用JVM的方法调用栈（隐式栈），代码更简洁，适合小规模图；
2. 非递归实现：显式创建栈对象，手动控制入栈/出栈，适合大规模图（避免栈溢出）。
   无论哪种方式，都需要访问标记数组/集合（如visited[]），标记顶点是否已被访问。

2.3 遍历步骤（以顶点A为起点，邻接顶点按字母序访问）

以包含顶点A、B、C、D、E、F、G、H、aoyou的连通图为例，步骤可概括为“入栈标记→深度探索→死胡同出栈→回溯再探索”，关键节点：

1. 起点 A 入递归调用栈，标记已访问，探索邻接顶点（字母序：B、D、G、aoyou），首先访问 B，B 入栈标记；
2. 从 B 探索未访问邻接顶点（字母序：E、F），首先访问 E，E 入栈标记；
3. E 无邻接顶点（或邻接点均无出边），为死胡同，回溯到 B；
4. B 继续探索下一个未访问邻接顶点 F，F 入栈标记；
5. 从 F 探索未访问邻接顶点 C，C 入栈标记；
6. 从 C 探索未访问邻接顶点 H，H 入栈标记；
7. H 无邻接顶点，回溯到 C；C 无其他邻接点，回溯到 F；F 无剩余未访问邻接点，回溯到 B；B 邻接点已全部访问，回溯到 A；
8. A 继续探索下一个未访问邻接顶点 D，D 入栈标记；
9. D 的邻接点为 E 和 F，但 E 和 F 均已被访问，D 无新路径，回溯到 A；
10. A 继续探索下一个未访问邻接顶点 G，G 入栈标记；
11. G 无邻接顶点，回溯到 A；
12. A 继续探索最后一个未访问邻接顶点 aoyou，aoyou 入栈标记；
13. aoyou 的邻接点为 G，但 G 已被访问，aoyou 无新路径，回溯到 A；
14. A 所有邻接点均已访问，递归结束，遍历完成。

遍历过程

2.4 代码实现（邻接表版，递归+非递归）

基于之前的邻接表图结构，实现DFS的递归版（简洁）和非递归版（通用），融入aoyou顶点，贴合示例要求：

import java.util.*; /** * 图的遍历：DFS（深度优先搜索） * 基于邻接表实现，包含递归+非递归版，融入aoyou顶点 * @author aoyou */ public class AoyouGraphDFS { // 顶点类：封装顶点名称和边链表 static class Vertex { String name; Edge next; public Vertex(String name, Edge next) { this.name = name; this.next = next; } } // 边类：封装目标顶点和权值 static class Edge { String target; int weight; Edge next; public Edge(String target, int weight, Edge next) { this.target = target; this.weight = weight; this.next = next; } } private Map<String, Vertex> vertexMap; // 存储所有顶点 private Set<String> visited; // 访问标记集合，替代数组（更灵活） public AoyouGraphDFS() { vertexMap = new HashMap<>(); visited = new HashSet<>(); } // 插入顶点 public void insertVertex(String name) { vertexMap.putIfAbsent(name, new Vertex(name, null)); } // 插入有向边：begin→end，权值weight public void insertEdge(String begin, String end, int weight) { Vertex beginV = vertexMap.get(begin); Edge newEdge = new Edge(end, weight, beginV.next); beginV.next = newEdge; // 头插法（不影响遍历，仅简化代码） // 无向图需额外插入end→begin的边 // insertEdge(end, begin, weight); } // 【DFS递归版】从指定起点开始遍历 public void dfsRecursive(String start) { if (!vertexMap.containsKey(start) || visited.contains(start)) { return; } // 1. 访问当前顶点：打印+标记 System.out.print(start + " → "); visited.add(start); // 2. 遍历当前顶点的所有邻接顶点，递归访问未标记的顶点 Vertex current = vertexMap.get(start); Edge edge = current.next; // 按字母序排序邻接顶点（保证遍历顺序一致） List<String> neighbors = new ArrayList<>(); while (edge != null) { neighbors.add(edge.target); edge = edge.next; } Collections.sort(neighbors); // 递归访问每个邻接顶点 for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { dfsRecursive(neighbor); } } } // 【DFS非递归版】从指定起点开始遍历（显式栈） public void dfsNonRecursive(String start) { if (!vertexMap.containsKey(start)) { return; } Stack<String> stack = new Stack<>(); Set<String> visited = new HashSet<>(); // 1. 起点入栈+标记 stack.push(start); visited.add(start); System.out.print("非递归DFS："); while (!stack.isEmpty()) { // 2. 出栈并访问当前顶点 String current = stack.pop(); System.out.print(current + " → "); // 3. 遍历邻接顶点，未标记的入栈+标记（逆序入栈，保证访问顺序为字母序） Vertex v = vertexMap.get(current); Edge edge = v.next; List<String> neighbors = new ArrayList<>(); while (edge != null) { neighbors.add(edge.target); edge = edge.next; } Collections.sort(neighbors, Collections.reverseOrder()); // 逆序 for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { stack.push(neighbor); visited.add(neighbor); } } } } // 重置访问标记（多次遍历用） public void resetVisited() { visited.clear(); } // 测试示例（无向图需注释掉边的单向插入） public static void main(String[] args) { AoyouGraphDFS graph = new AoyouGraphDFS(); // 1. 插入顶点（包含A、B、C、D、E、F、G、H、aoyou） String[] vertexes = {"A", "B", "C", "D", "E", "F", "G", "H", "aoyou"}; for (String v : vertexes) { graph.insertVertex(v); } // 2. 插入有向边（模拟连通图） graph.insertEdge("A", "B", 4); graph.insertEdge("A", "D", 5); graph.insertEdge("A", "G", 1); graph.insertEdge("A", "aoyou", 8); graph.insertEdge("B", "E", 2); graph.insertEdge("B", "F", 3); graph.insertEdge("D", "F", 4); graph.insertEdge("D", "E", 3); graph.insertEdge("F", "C", 2); graph.insertEdge("C", "H", 5); graph.insertEdge("aoyou", "G", 2); // aoyou连接G // 3. 递归版DFS（起点A） System.out.print("递归版DFS："); graph.dfsRecursive("A"); System.out.println("结束"); // 4. 非递归版DFS（起点A） graph.dfsNonRecursive("A"); System.out.println("结束"); } }

2.5 运行结果

递归版DFS：A → B → E → F → C → H → D → G → aoyou → 结束 非递归DFS：A → B → E → F → C → H → D → G → aoyou → 结束

2.6 时间复杂度

DFS的时间复杂度与图的存储方式相关，取决于访问所有顶点和遍历所有边的开销：

邻接矩阵存储：查找每个顶点的邻接顶点需遍历整行，耗时

，总时间复杂度

。

邻接表存储：访问所有顶点耗时

（V为顶点数），遍历所有边耗时

（E为边数），总时间复杂度

；

2.7 应用场景

DFS专注于“是否存在路径”，不关心路径长度，典型应用：

• 判断图的连通性（无向图是否为连通图、有向图是否强连通）；
• 寻找图中的环（如检测任务依赖是否有循环）；
• 拓扑排序（有向无环图DAG）、迷宫探索、排列组合问题；
• 深度优先的搜索遍历（如文件夹的递归遍历，本质是树的DFS）。

三、广度优先搜索（BFS，Breadth First Search）

3.1 思想

BFS的是“广度优先，层层推进”，类似水面波纹扩散：从起点出发，先访问起点的所有邻接顶点（第一层），再依次访问第一层每个顶点的邻接顶点（第二层），以此类推，直到遍历所有顶点。
简单总结：先广后深，层层遍历。

3.2 实现依赖

BFS的实现依赖队列（Queue）（先进先出FIFO），必须显式实现（无递归版），同时需要访问标记数组/集合，原因：队列保证“层层推进”的顺序，标记避免同一顶点被多次入队。

3.3 遍历步骤（以顶点A为起点，邻接顶点按字母序入队）

以上述连通图为例，BFS的是“入队标记→出队访问→邻接顶点入队标记”，层层遍历：

1. 起点A入队，标记已访问；
2. A出队并访问，将A的邻接顶点B、D、G、aoyou（字母序）依次入队，标记已访问（第一层）；
3. B出队并访问，将B的未访问邻接顶点E、F入队，标记（第二层）；
4. D出队并访问，其邻接顶点均已标记，无入队；G出队并访问，无未访问邻接顶点；aoyou出队并访问，无未访问邻接顶点；
5. E出队并访问，无未访问邻接顶点；F出队并访问，将F的未访问邻接顶点C入队，标记（第三层）；
6. C出队并访问，将C的未访问邻接顶点H入队，标记（第四层）；
7. H出队并访问，无未访问邻接顶点；队列为空，遍历结束。

遍历过程

3.4 代码实现（邻接表版，求解最短路径）

基于同一邻接表结构，实现BFS遍历，并增加无权图最短路径求解功能（BFS的经典应用）：

import java.util.*; /** * 图的遍历：BFS（广度优先搜索） * 基于邻接表实现，含遍历+无权图最短路径求解 * @author aoyou */ public class AoyouGraphBFS { // 复用顶点类和边类（与DFS一致，省略） static class Vertex { String name; Edge next; public Vertex(String name, Edge next) { this.name = name; this.next = next; } } static class Edge { String target; int weight; Edge next; public Edge(String target, int weight, Edge next) { this.target = target; this.weight = weight; this.next = next; } } private Map<String, Vertex> vertexMap; public AoyouGraphBFS() { vertexMap = new HashMap<>(); } // 插入顶点、插入边（与DFS一致，省略） public void insertVertex(String name) { vertexMap.putIfAbsent(name, new Vertex(name, null)); } public void insertEdge(String begin, String end, int weight) { Vertex beginV = vertexMap.get(begin); Edge newEdge = new Edge(end, weight, beginV.next); beginV.next = newEdge; // 无向图请添加：insertEdge(end, begin, weight); } // 【BFS遍历】从指定起点遍历所有顶点 public void bfsTraverse(String start) { if (!vertexMap.containsKey(start)) { System.out.println("起点顶点不存在！"); return; } Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); // 起点入队+标记 queue.offer(start); visited.add(start); System.out.print("BFS遍历序列："); while (!queue.isEmpty()) { // 出队并访问当前顶点 String current = queue.poll(); System.out.print(current + " → "); // 遍历邻接顶点，未标记的入队+标记（按字母序） Vertex v = vertexMap.get(current); Edge edge = v.next; List<String> neighbors = new ArrayList<>(); while (edge != null) { neighbors.add(edge.target); edge = edge.next; } Collections.sort(neighbors); for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { queue.offer(neighbor); visited.add(neighbor); } } } System.out.println("结束"); } // 【BFS经典应用】求解无权图中起点到目标顶点的最短路径（边数） public int bfsShortestPath(String start, String target) { if (!vertexMap.containsKey(start) || !vertexMap.containsKey(target)) { return -1; // 顶点不存在，返回-1表示不可达 } if (start.equals(target)) { return 0; // 起点=目标，路径长度0 } Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); Map<String, Integer> pathLen = new HashMap<>(); // 记录每个顶点到起点的路径长度 // 初始化 queue.offer(start); visited.add(start); pathLen.put(start, 0); while (!queue.isEmpty()) { String current = queue.poll(); // 遍历邻接顶点 Vertex v = vertexMap.get(current); Edge edge = v.next; while (edge != null) { String neighbor = edge.target; if (neighbor.equals(target)) { return pathLen.get(current) + 1; // 找到目标，返回路径长度 } if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); pathLen.put(neighbor, pathLen.get(current) + 1); } edge = edge.next; } } return -1; // 无路径可达 } // 测试示例 public static void main(String[] args) { AoyouGraphBFS graph = new AoyouGraphBFS(); // 1. 插入顶点（A、B、C、D、E、F、G、H、aoyou） String[] vertexes = {"A", "B", "C", "D", "E", "F", "G", "H", "aoyou"}; for (String v : vertexes) { graph.insertVertex(v); } // 2. 插入有向边 graph.insertEdge("A", "B", 4); graph.insertEdge("A", "D", 5); graph.insertEdge("A", "G", 1); graph.insertEdge("A", "aoyou", 8); graph.insertEdge("B", "E", 2); graph.insertEdge("B", "F", 3); graph.insertEdge("D", "F", 4); graph.insertEdge("D", "E", 3); graph.insertEdge("F", "C", 2); graph.insertEdge("C", "H", 5); graph.insertEdge("aoyou", "G", 2); // 3. BFS遍历（起点A） graph.bfsTraverse("A"); // 4. 求解最短路径（无权图） System.out.println("A到aoyou的最短路径长度：" + graph.bfsShortestPath("A", "aoyou")); System.out.println("A到H的最短路径长度：" + graph.bfsShortestPath("A", "H")); System.out.println("aoyou到H的最短路径长度：" + graph.bfsShortestPath("aoyou", "H")); } }

3.5 运行结果

BFS遍历序列：A → B → D → G → aoyou → E → F → C → H → 结束 A到aoyou的最短路径长度：1 A到H的最短路径长度：4 aoyou到H的最短路径长度：-1

3.6 时间复杂度

BFS的时间复杂度与DFS完全一致，仅依赖存储方式，与遍历策略无关：

1. 邻接表存储：访问顶点 + 遍历边 → 总；
2. 邻接矩阵存储：查找邻接顶点 → 总。

3.7 应用场景

BFS专注于“最短路径”（无权图），层层推进的特性使其适合多源遍历，典型应用：

• 求解无权图的最短路径（如迷宫的最短走出路线、社交网络的一度/二度好友）；
• 社交网络的好友推荐（一度好友、二度好友查找，层层推进）；
• 多源BFS（如洪水填充、地图上的多起点路径规划）；
• 双端BFS（从起点和终点同时BFS，大幅提升长路径搜索效率）；
• 图的连通性判断、层序遍历（如二叉树的层序遍历是特殊的BFS）。

四、DFS与BFS对比

从思想、辅助结构、访问顺序、适用场景等8个维度做全面对比，是实际开发中选择遍历算法的关键依据：

五、注意事项

1. 访问标记是必须的：图存在环，必须用visited数组/集合标记已访问顶点，否则会陷入无限循环；
2. 非连通图的遍历：上述代码均基于连通图，若图为非连通图，需遍历所有顶点，对未标记的顶点重新执行DFS/BFS；
3. 邻接顶点的访问顺序：遍历结果不唯一，依赖邻接顶点的访问顺序（如字母序、插入序），可通过排序保证顺序一致；
4. 有向图与无向图的适配：无向图的边是双向的，插入边时需同时插入u→v和v→u，否则会出现遍历不完整；
5. 栈溢出问题：递归版DFS适合小规模图，大规模图需用非递归版DFS（显式栈），避免JVM方法栈溢出；
6. 最短路径的适用范围：BFS仅能求解无权图的最短路径，带权图的最短路径需用Dijkstra、Floyd等算法。

六、总结

1. 图的遍历要求访问所有顶点且仅访问一次，因图有环和多对多连接，访问标记是实现的关键，分为DFS和BFS两种策略；
2. DFS基于栈实现，是“深度优先、回溯探索”，适合判断连通性，不保证最短路径，有递归（简洁）和非递归（通用）两种实现；
3. BFS基于队列实现，是“地毯式层层推进”，是无权图最短路径的最优解，典型应用为社交网络好友查找、迷宫最短路径；
4. DFS和BFS的时间复杂度一致：邻接表存储，邻接矩阵存储，空间复杂度均为最坏；
5. 实际开发中，根据业务需求选择算法：判断是否存在路径用DFS，求解无权图最短路径用BFS；
6. 非连通图需遍历所有顶点，对未标记顶点重新执行遍历；无向图插入边时需双向插入，保证遍历完整。