Breadth-first search

Breadth-first-tree

Animated_BFS

Error creating thumbnail:

BFS-Algorithm_Search_Way

Error creating thumbnail:

Tic-tac-toe-game-tree

MapGermanyGraph

Error creating thumbnail:

GermanyBFS

Algorithm for searching a tree or graph

Template:Algorithm

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node in the case of a graph) and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Algorithm

The BFS algorithm works as follows:

1. Start by placing the root node in a queue.
2. Mark the root node as visited.
3. While the queue is not empty:
   1. Remove the node at the front of the queue.
   2. For each of the node's neighbors:
      1. If the neighbor has not been visited:
         1. Mark it as visited.
         2. Add it to the queue.

Properties

• Completeness: BFS is complete, meaning it will find a solution if one exists.
• Optimality: BFS is optimal if all edges have the same cost.
• Time complexity: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges.
• Space complexity: The space complexity of BFS is O(V), where V is the number of vertices.

Applications

BFS is used in various applications, including:

• Finding the shortest path in an unweighted graph.
• Web crawling.
• Social network analysis.
• Broadcasting in computer networks.
• Garbage collection in computer science.

Pseudocode

Here is a pseudocode representation of the BFS algorithm:

``` BFS(G, start_vertex):

 create a queue Q
 enqueue start_vertex onto Q
 mark start_vertex as visited
 while Q is not empty:
   current_vertex = dequeue Q
   for each neighbor of current_vertex:
     if neighbor has not been visited:
       mark neighbor as visited
       enqueue neighbor onto Q

```

Related Algorithms

• Depth-first search
• Dijkstra's algorithm
• A* search algorithm

See Also

• Graph theory
• Tree (data structure)
• Queue (abstract data type)
• Algorithm

Related Pages

• Graph traversal
• Search algorithm
• Shortest path problem
• Computer science