图的遍历：广度优先搜索（BFS）

引言

图遍历是指按照一定的顺序访问图中的每个顶点。遍历图的两种主要方法是深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。本文将详细介绍广度优先搜索的定义、算法及其实现。

广度优先搜索（BFS）

定义

广度优先搜索（BFS）是一种遍历或搜索图的算法，从图的某个起始顶点开始，首先访问距离起始顶点最近的顶点，然后依次访问距离更远的顶点。BFS 使用队列（Queue）数据结构来实现。

算法步骤

1. 从起始顶点开始，将其标记为已访问并入队。
2. 当队列不为空时，进行以下操作：
   1. 从队列中取出一个顶点，访问该顶点。
   2. 将所有未被访问的邻接顶点标记为已访问并入队。

示例

假设我们有一个无向图，顶点集合为 ({A, B, C, D, E, F})，边集合为 ({(A, B), (A, C), (B, D), (C, E), (D, F)})。

BFS实现

下面是用Java实现BFS的代码示例：

import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    private LinkedList<Integer>[] adjLists; // 邻接表数组
    private boolean[] visited; // 访问标记数组

    // 构造函数
    public Graph(int numVertices) {
        adjLists = new LinkedList[numVertices];
        visited = new boolean[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjLists[i] = new LinkedList<>();
        }
    }

    // 添加边
    public void addEdge(int i, int j) {
        adjLists[i].add(j);
        adjLists[j].add(i); // 无向图
    }

    // 广度优先搜索
    public void BFS(int startVertex) {
        Queue<Integer> queue = new LinkedList<>();
        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int adj : adjLists[vertex]) {
                if (!visited[adj]) {
                    visited[adj] = true;
                    queue.add(adj);
                }
            }
        }
    }

    // 打印邻接表
    public void printAdjLists() {
        for (int i = 0; i < adjLists.length; i++) {
            System.out.print(i + ": ");
            for (int j : adjLists[i]) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);

        System.out.println("图的邻接表表示：");
        graph.printAdjLists();

        System.out.println("广度优先搜索遍历结果：");
        graph.BFS(0); // 输出：0 1 2 3 4 5
    }
}

测试代码的运行结果：

• 邻接表表示：

0: 1 2 
1: 0 3 
2: 0 4 
3: 1 5 
4: 2 
5: 3 

• 广度优先搜索遍历结果：0 1 2 3 4 5

BFS算法步骤图解

以下是对上述示例中BFS算法步骤的图解：

结论

通过上述讲解和实例代码，我们详细展示了广度优先搜索（BFS）的定义、算法及其实现。BFS是一种重要的图遍历算法，广泛应用于各种场景。希望这篇博客对您有所帮助！

如果您觉得这篇文章对您有帮助，请关注我的CSDN博客，点赞并收藏这篇文章，您的支持是我持续创作的动力！

关键内容总结：

• 广度优先搜索（BFS）的定义
• BFS算法的步骤
• BFS的实现及其图解

推荐阅读：深入探索设计模式专栏，详细讲解各种设计模式的应用和优化。点击查看：深入探索设计模式。

特别推荐：设计模式实战专栏，深入解析设计模式的实际应用，提升您的编程技巧。点击查看：设计模式实战。

如有任何疑问或建议，欢迎在评论区留言讨论。谢谢阅读！