图遍历算法详解：DFS 与 BFS 原理及 Java 实现

以包含顶点 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 顶点
 */
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 的时间复杂度与图的存储方式相关，取决于访问所有顶点和遍历所有边的开销：

邻接矩阵存储：查找每个顶点的邻接顶点需遍历整行，耗时 O(V^2)，总时间复杂度 O(V^2)。

邻接表存储：访问所有顶点耗时 O(V)（V 为顶点数），遍历所有边耗时 O(E)（E 为边数），总时间复杂度 O(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（广度优先搜索）
 * 基于邻接表实现，含遍历 + 无权图最短路径求解
 */
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. 邻接表存储：访问顶点 + 遍历边 → 总 O(V+E)；
2. 邻接矩阵存储：查找邻接顶点 → 总 O(V^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 的时间复杂度一致：邻接表存储 O(V+E)，邻接矩阵存储 O(V^2)，空间复杂度均为最坏 O(V)；
5. 实际开发中，根据业务需求选择算法：判断是否存在路径用 DFS，求解无权图最短路径用 BFS；
6. 非连通图需遍历所有顶点，对未标记顶点重新执行遍历；无向图插入边时需双向插入，保证遍历完整。