在访问给定数据结构中的数据时，搜索或者遍历非常重要。在这些数据结构(如图和树)中有不同的遍历/搜索元素的方法。

广度优先搜索就是这些方法的一个例子。BFS是一种遍历树或者图的算法，它从树根(树中最顶端的节点)或者仅仅从树的顶部开始，扫描当前深度的所有相邻节点，然后再转到下一个深度的节点/元素。

简单地说，BFS必须完成一个图层，然后继续下一个图层，直到没有剩下的图层。

BFS使用完全相反的工作流作为深度优先搜索，而深度优先搜索则相反。

BFS和DFS在实现方面的一个很大区别是BFS使用队列，而DFS使用堆栈。

BFS工作流程

BFS的实现

在实现BFS时，有两个简单的规则要遵循：

访问给定层上的每个元素

继续下一层

例如：

在进入第二层之前，第一层必须先经过。

之后，应该这样做：

伪码

**

public void breadthFirstSearch(Graph G, Object S)
//G => Graph ; S => Source node
{
   define a queue named as Queue;
   insert the source node in the Q
   mark s as visited

   perform a while loop that keeps looping until the queue is not empty
      removing the current element from the queue as it will be visited now

      perform a for loop that goes through all neighbours of the current element
          if condition that checks if the current element/node/vertex is not visited
              if it has not been visited, enqueue it and mark it as visited
}

实际代码实现

public void BFS(int s, int l) 
  { 
      //create an array that holds boolean values that will have length 'l'
      boolean visited[] = new boolean[l]; 

      //create a queue
      LinkedList<Integer> q = new LinkedList<Integer>(); 

      //mark the current node as visited and add it to the queue
      visited[s]=true; 
      q.add(s); 

      while (q.size() != 0) 
      { 
          //dequeuing a vertex from queue 
          s = q.poll(); 

          //get all adjacent vertices of the dequeued vertex  if a adjacent has not 
          //been visited, then mark it visited and enqueue it 
          Iterator<Integer> k = adj[s].listIterator(); 
          while (k.hasNext()) 
          { 
              int j = k.next(); 
              if (!visited[j]) 
              { 
                  visited[j] = true; 
                  q.add(j); 
              } 
          } 
      } 
  }