02_02_广度优先搜索（Breadth-First Search，BFS）

2023-11-08

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

广度优先搜索（Breadth-First Search，BFS）介绍：

是一种图遍历算法，其原理是逐层遍历图的节点。BFS从起始节点开始，先访问起始节点的所有邻居节点，然后再逐层访问其他邻居节点。

广度优先搜索（Breadth-First Search，BFS）原理：

选择一个起始节点，并将其标记为已访问。
将起始节点放入队列（通常是使用队列数据结构实现BFS）。
当队列不为空时，执行以下步骤：
● 从队列中取出一个节点作为当前节点。
● 访问当前节点，并进行相应的操作。
● 将当前节点的所有未访问的邻居节点加入队列，并标记为已访问。
如果队列为空，表示已经遍历完所有节点，算法结束。

Java 代码实现：

package com.algorithm.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

    /**
     * 测试方法
     *
     * @param args todo
     */
    public static void main(String[] args) {

        /**
         * 创建有 6 个节点的图对象
         */
        BFSGraph graph = new BFSGraph(6);

        /**
         * 添加节点
         */
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);

        System.out.println("Breadth-First Traversal (starting from vertex 0):");

        /**
         * 调用 BFS 算法遍历节点
         */
        graph.BFS(0);
    }

}

/**
 * BFS 算法实现原理
 * <p>
 * 1.选择一个起始节点，并将其标记为已访问。
 * 2.将起始节点放入队列（通常是使用队列数据结构实现BFS）。
 * 3.当队列不为空时，执行以下步骤：
 * 从队列中取出一个节点作为当前节点。
 * 访问当前节点，并进行相应的操作。
 * 将当前节点的所有未访问的邻居节点加入队列，并标记为已访问。
 * 4.如果队列为空，表示已经遍历完所有节点，算法结束。
 */
class BFSGraph {

    /**
     * 节点数量
     */
    private int numVertices;

    /**
     * 邻接表
     */
    private List<List<Integer>> adjacencyList;

    /**
     * 构造方法，将所有的节点全部存储在 ArrayList 集合中
     *
     * @param numVertices 节点数量
     */
    public BFSGraph(int numVertices) {
        this.numVertices = numVertices;
        this.adjacencyList = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    /**
     * 添加边到邻接表
     *
     * @param source      起始节点
     * @param destination 终点节点
     */
    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination);
        /**
         * 如果是无向图，需要添加反向边
         */
        adjacencyList.get(destination).add(source);
    }

    /**
     * 算法实现
     *
     * @param startVertex 开始节点
     */
    public void BFS(int startVertex) {

        /**
         * 标记节点是否已被访问
         */
        boolean[] visited = new boolean[numVertices];

        /**
         * 使用队列来存储待访问的节点
         */
        Queue<Integer> queue = new LinkedList<>();

        /**
         * 从起始节点开始，将其标记为已访问并加入队列
         * 队列特点：先入先出
         */
        visited[startVertex] = true;
        queue.add(startVertex);

        /**
         * 遍历队列
         */
        while (!queue.isEmpty()) {
            int currentVertex = queue.poll();

            /**
             * 打印节点
             */
            System.out.print(currentVertex + " ");

            List<Integer> neighbors = adjacencyList.get(currentVertex);
            for (int neighbor : neighbors) {
                if (!visited[neighbor]) {
                    /**
                     *将未访问的邻居节点标记为已访问
                     */
                    visited[neighbor] = true;

                    /**
                     * 将节点加入队列
                     */
                    queue.add(neighbor);
                }
            }
        }
    }
}

代码简单解释：

在这个代码示例中，我们定义了一个Graph类来表示图数据结构，包括节点数量numVertices和邻接表adjacencyList。addEdge方法用于添加边到邻接表，注意在无向图中需要添加反向边。

在BFS方法中，我们使用一个布尔数组visited来标记节点是否已被访问，并使用一个队列queue来存储待访问的节点。我们从起始节点开始，将其标记为已访问并入队列。然后，进入循环直到队列为空。在循环中，我们从队列中取出一个节点，打印该节点，并将其未访问的邻居节点标记为已访问并入队列。

在主函数中，我们创建一个Graph对象，并通过addEdge方法添加边。然后调用BFS方法以广度优先的方式遍历图，从起始节点0开始。

程序执行结果：

Breadth-First Traversal (starting from vertex 0):
0 1 2 3 4 5 
Process finished with exit code 0

备注：

广度优先搜索算法的原理是逐层遍历，从起始节点开始，先访问起始节点的所有邻居节点，然后逐层访问下一层的邻居节点。这样可以保证从起始节点到其他节点的最短路径被优先访问到。BFS算法还可以用于解决一些问题，如寻找最短路径、连通性检测、图的遍历等。

广度优先搜索（Breadth-First Search，BFS）算法图示:

假设我们有以下图结构：

开始时，选择起始节点0进行广度优先搜索。我们从节点0开始，然后按照层级逐层访问节点的邻居节点。首先，我们访问节点0的邻居节点1和2。然后，访问节点1的邻居节点3，访问节点2的邻居节点4和5。

下面是BFS算法执行的过程描述：

选择起始节点0，并将其标记为已访问。

访问节点0的邻居节点1和2，并将它们标记为已访问。

访问节点1的邻居节点3，并将其标记为已访问。

访问节点2的邻居节点4和5，并将它们标记为已访问。

     0*
    / \
   1*  2*
  /   / \
 3*  4*  5*

最终，BFS算法的遍历路径为0-1-2-3-4-5。

总结：

通过图的可视化，我们可以更直观地理解BFS算法的执行过程。在每一层级中，我们先访问当前层级的所有节点，然后再进入下一层级的节点。这种层级遍历的方式可以帮助我们找到起始节点到其他节点的最短路径，并保证我们按照距离逐层遍历图的节点。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)