什么是广度优先搜索算法

遍历意味着访问图的所有节点。广度优先遍历或广度优先搜索是一种递归算法，用于搜索图或树数据结构的所有顶点。标准的 BFS 实现将图的每个顶点放入以下两类之一：

访问过的顶点
未访问的顶点

该算法的目的是将每个顶点标记为已访问，同时避免循环。该算法的工作原理如下：

首先将图的任何一个顶点放在队列的后面。
取队列的最前面的项目并将其添加到访问列表中。
创建该顶点的相邻节点的列表。将不在访问列表中的添加到队列的后面。
继续重复步骤 2 和 3，直到队列为空。

该图可能有两个不同的不连接部分，因此为了确保我们覆盖每个顶点，我们还可以在每个节点上运行 BFS 算法

广度优先算法算法与队列

让我们通过一个例子来看看广度优先搜索算法是如何工作的。我们使用具有 5 个顶点的无向图。


具有 5 个顶点的无向图

我们从顶点 0 开始，BFS 算法首先将其放入访问列表并将其所有相邻顶点放入堆栈中。


访问起始顶点并将其相邻顶点加入队列

接下来，我们访问队列前面的元素，即 1 并转到其相邻节点。由于 0 已经被访问过，我们改为访问 2。


访问起始节点0的第一个邻居，即1

顶点 2 在 4 中有一个未访问的相邻顶点，因此我们将其添加到队列的后面并访问位于队列前面的 3。


访问 2 之前添加到队列以添加其邻居


4 仍在队列中

由于 3 的唯一相邻节点（即 0）已被访问，因此队列中仅剩下 4 个。


访问堆栈中的最后一个剩余项目以检查它是否有未访问的邻居

由于队列为空，我们就完成了图的广度优先遍历。

广度优先搜索算法复杂度

BFS算法的时间复杂度以O(V+E)的形式表示，其中V是节点数，E是边数。
该算法的空间复杂度为 O(V)。

广度优先搜索算法的应用

通过搜索索引建立索引
用于 GPS 导航
寻路算法
在 Ford-Fulkerson 算法中寻找网络中的最大流量
无向图中的循环检测
在最小生成树中

广度优先搜索算法的伪码

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

广度优先搜索算法的实现

// BFS algorithm in Java

import java.util.*;

public class Graph {
  private int V;
  private LinkedList<Integer> adj[];

  // Create a graph
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  // Add edges to the graph
  void addEdge(int v, int w) {
    adj[v].add(w);
  }

  // BFS algorithm
  void BFS(int s) {

    boolean visited[] = new boolean[V];

    LinkedList<Integer> queue = new LinkedList();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }

  public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");

    g.BFS(2);
  }
}