Javajava算法
图遍历算法详解：DFS 与 BFS 原理及 Java 实现
图的两种核心遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）。内容涵盖定义、思想、实现依赖（栈与队列）、步骤演示、Java 代码实现（递归与非递归）、时间复杂度分析及应用场景。通过邻接表结构，展示了如何避免重复访问、处理非连通图及求解无权图最短路径。对比了两者在辅助结构、访问顺序及适用场景上的差异，为实际开发中根据需求选择合适算法提供依据。
图的两种核心遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）。内容涵盖定义、思想、实现依赖（栈与队列）、步骤演示、Java 代码实现（递归与非递归）、时间复杂度分析及应用场景。通过邻接表结构，展示了如何避免重复访问、处理非连通图及求解无权图最短路径。对比了两者在辅助结构、访问顺序及适用场景上的差异，为实际开发中根据需求选择合适算法提供依据。
图的遍历是指从图中任意指定顶点（初始点）出发，按照特定搜索策略沿着边访问所有顶点且每个顶点仅访问一次的过程，遍历得到的顶点序列称为遍历序列。
要求：全访问、不重复——这是因为图存在环和多对多连接，相比二叉树（无环、一对多），遍历需增加访问标记避免重复访问，是图遍历的关键要点。
根据访问顶点的顺序不同，图的遍历分为深度优先搜索（DFS）和广度优先搜索（BFS），二者是图论中最基础、应用最广泛的算法，分别基于栈和队列实现，适配不同的业务场景：
二叉树的前/中/后序遍历本质是特殊的图遍历（二叉树是无环的连通图），但图的遍历更复杂，差异如下：
| 对比维度 | 二叉树遍历 | 图的遍历 |
|---|---|---|
| 结构特性 | 无环、一对多、连通 | 可能有环、多对多、可能非连通 |
| 访问标记 | 无需（无重复路径） | 必须有（数组/集合标记，避免环导致重复访问） |
| 辅助结构 | 递归（隐式栈）/显式栈 | DFS 用栈、BFS 用队列 |
| 遍历结果 | 唯一（固定左右子树顺序） | 不唯一（依赖邻接顶点的访问顺序） |
DFS 的是**'深度优先，回溯探索'，类似走迷宫：从起点出发，选择一个方向一直往前走，直到走到'死胡同'（当前顶点无未访问的邻接顶点），再回溯到上一个顶点，尝试其他未走的方向，直到遍历所有顶点。
简单总结：先深后广，遇阻回溯。
DFS 的实现依赖栈（Stack）（后进先出 LIFO），有两种实现方式：
visited[]），标记顶点是否已被访问。
以包含顶点 A、B、C、D、E、F、G、H、aoyou 的连通图为例，步骤可概括为**'入栈标记→深度探索→死胡同出栈→回溯再探索'**，关键节点：
遍历过程
基于之前的邻接表图结构，实现 DFS 的递归版（简洁）和非递归版（通用），融入 aoyou 顶点，贴合示例要求：
import java.util.*;
/**
* 图的遍历：DFS（深度优先搜索）
* 基于邻接表实现，包含递归 + 非递归版，融入 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("结束");
}
}
递归版 DFS：A → B → E → F → C → H → D → G → aoyou → 结束 非递归 DFS：A → B → E → F → C → H → D → G → aoyou → 结束
DFS 的时间复杂度与图的存储方式相关，取决于访问所有顶点和遍历所有边的开销：
邻接矩阵存储：查找每个顶点的邻接顶点需遍历整行，耗时 O(V^2)，总时间复杂度 O(V^2)。
邻接表存储：访问所有顶点耗时 O(V)（V 为顶点数），遍历所有边耗时 O(E)（E 为边数），总时间复杂度 O(V+E)；
DFS 专注于**'是否存在路径'**，不关心路径长度，典型应用：
BFS 的是**'广度优先，层层推进'**，类似水面波纹扩散：从起点出发，先访问起点的所有邻接顶点（第一层），再依次访问第一层每个顶点的邻接顶点（第二层），以此类推，直到遍历所有顶点。
简单总结：先广后深，层层遍历。
BFS 的实现依赖队列（Queue）（先进先出 FIFO），必须显式实现（无递归版），同时需要访问标记数组/集合，原因：队列保证'层层推进'的顺序，标记避免同一顶点被多次入队。
以上述连通图为例，BFS 的是**'入队标记→出队访问→邻接顶点入队标记'**，层层遍历：
遍历过程
基于同一邻接表结构，实现 BFS 遍历，并增加无权图最短路径求解功能（BFS 的经典应用）：
import java.util.*;
/**
* 图的遍历：BFS（广度优先搜索）
* 基于邻接表实现，含遍历 + 无权图最短路径求解
*/
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"));
}
}
BFS 遍历序列：A → B → D → G → aoyou → E → F → C → H → 结束 A 到 aoyou 的最短路径长度：1 A 到 H 的最短路径长度：4 aoyou 到 H 的最短路径长度：-1
BFS 的时间复杂度与 DFS完全一致，仅依赖存储方式，与遍历策略无关：
BFS 专注于**'最短路径'**（无权图），层层推进的特性使其适合多源遍历，典型应用：
从思想、辅助结构、访问顺序、适用场景等 8 个维度做全面对比，是实际开发中选择遍历算法的关键依据：
| 对比维度 | 深度优先搜索（DFS） | 广度优先搜索（BFS） |
|---|---|---|
| 思想 | 深度优先，一条路走到黑，遇阻回溯 | 广度优先，地毯式层层推进，逐层遍历 |
| 辅助结构 | 栈（递归：隐式方法栈；非递归：显式栈） | 队列（LinkedList，显式实现） |
| 访问顺序 | 先深后广，不按距离排序 | 先广后深，按到起点的距离（边数）排序 |
| 特性 | 不保证最短路径，适合连通性判断 | 保证无权图的最短路径，适合路径求解 |
| 空间复杂度 | 最坏 O(V)（栈存储顶点） | 最坏 O(V)（队列存储顶点） |
| 时间复杂度 | 邻接表 O(V+E)，邻接矩阵 O(V^2) | 与 DFS 完全一致 |
| 实现方式 | 递归（简洁）、非递归（通用） | 仅显式队列实现（无递归） |
| 典型应用 | 连通性判断、找环、拓扑排序、迷宫探索 | 无权图最短路径、好友推荐、双端 BFS、洪水填充 |
visited 数组/集合标记已访问顶点，否则会陷入无限循环；u→v 和 v→u，否则会出现遍历不完整；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online