Breadth First Search or BFS for a Graph in Java

广度优先搜索（BFS）是一种基本的搜索算法，用于遍历树或图。在BFS中，从给定的源节点开始，按递增顺序遍历节点，并在进入下一级别之前探索完特定级别上的所有节点。

该算法在诸如无权图的最短路径搜索或搜索到源节点的给定距离内的所有节点等情况下非常有用。

BFS如何工作？

BFS 通过从源节点扩展到其所有直接邻居，然后再到邻居的邻居来工作。它采用队列数据结构来存储待处理的节点，以研究需要进行处理操作的节点。

当一个节点被处理时，其尚未访问过的邻居将被入队。这确保了在图中，所有节点都以反映与源节点距离的方式被覆盖。

BFS中的步骤

1. 将源节点入队并将其标记为已访问。
2. 出队一个节点，探索其所有未访问过的邻居，并将它们标记为已访问。
3. 将每个未访问的邻居入队，并重复此过程，直到队列为空。

BFS算法使用以下组件

• 一个队列，用于跟踪要访问的节点。
• 一个已访问数组（或集合），以避免重复访问节点。

BFS 算法

让我们逐步了解BFS的逻辑

1. 创建一个队列并将起始节点（源）入队。
2. 将源节点标记为已访问。
3. 当队列不为空时
   
   • 从队列前端出队一个节点。
   • 对于出队节点的每个相邻节点，如果它尚未被访问
     
     • 将其标记为已访问。
     • 将相邻节点入队。

让我们在一个 Java 程序中实现上述算法。

文件名：BFSGraph.java

输出

 
BFS traversal starting from node 0:
0 1 2 3 4 5  

解释

广度优先搜索（BFS）是最重要的搜索算法之一，用于通过逐渐增长的级别访问节点来检查图和树。它以先进先出（FIFO）的方式处理节点，即在移至下一级别之前必须访问同一级别的所有节点。

BFS在节点被访问后会进行检查，以避免重复访问并因此形成循环。它通过将源节点入队开始，然后处理源节点的邻居，如果它们尚未被访问过，则将它们入队。

BFS在确定无权图中的最短路径以及到起始节点给定半径内的所有可达节点方面非常有用。广度优先搜索算法中有两个操作，其时间复杂度为 V + E，其中 V 是图中顶点的数量，E 是边数，因此它对于图遍历问题非常高效。它的时间复杂度为 O(V)，因为需要存储队列以及已访问的节点。

复杂度分析

时间复杂度：BFS算法遍历每个顶点并遍历图中的每条边一次。因此，它需要 O(V + E) 的时间，V 代表顶点的数量，E 代表边的数量。

空间复杂度：空间复杂度为 O(V)，主要驱动力是算法中使用的队列以及已访问的数组。