Breadth-first search (BFS) searches tree data structures for nodes with a particular property. 

In a chess endgame, for instance, a chess engine may construct the game tree by applying all potential moves to the present situation and then utilise breadth-first search to identify a victory position for white. The size of implicit trees (such as game trees and other problem-solving trees) may be unlimited, yet, a breadth-first search is guaranteed to locate a solution node if one exists. 

In contrast, a (basic) depth-first search may get stuck in an infinite branch and never reach the solution node. Iterative deepening depth-first search circumvents this disadvantage by repeatedly searching the tree's upper branches. In contrast, neither of the depth-first techniques requires more memory. Moreover, when the start node is explicitly specified, and precautions are made to avoid following a vertex twice, the breadth-first search can be generalised to graphs.

Implementation of BFS traversal

To implement BFS traversal, use the method outlined below.

• Declare a queue and add the initial vertex to it.
• Mark the initial vertex of the visited array as visited.
• Follow the steps below until the line is empty:
• Remove the initial vertex from the list.
• Mark visited this vertex.
• Insert into the queue all unvisited neighbours of the vertex.

Now, we will examine the Python source code for the programme that implements breadth-first search.

Consider the following graph implemented with the following code:

Image source: Hackerearth

Python Code:

graph = {
  '0' : ['1','2','3'],
  '1' : ['4', '5'],
  '4' : [],
  '5' : [],
  '2' : ['6','7'],
  '6' : [],
  '3' : ['7'],
  '7' : []
}

visited = [] # List for visited nodes.
queue = [] #Initialize a queue

def bfs(visited, graph, node): #function for BFS
  visited.append(node)
  queue.append(node)

  while queue: # Creating loop to visit each node
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '0')

Output:

Following is the Breadth-First Search
> 
0 1 2 3 4 5 6 7 > 

Conclusion

In the analysis of algorithms, it is assumed that the input to the breadth-first search is a finite graph represented by an adjacency list, adjacency matrix, or a similar representation. However, artificial intelligence graph traversal applications may use implicit terms of unending graphs. In this context, a search strategy is complete if it is guaranteed to locate a goal state if it exists. The breadth-first search is exhaustive, whereas the depth-first search is incomplete. When applied to infinite graphs represented implicitly, the breadth-first search will ultimately locate the goal state, whereas the depth-first search may become lost in portions of the graph that lack a goal and never return.

Applications

We can utilise breadth-first search to tackle numerous problems in graph theory, including:

• Cheney's algorithm mimics garbage collection.
• Finding the shortest edge-length path between two nodes, u and v.
• Cuthill–McKee mesh identification
• The Ford–Fulkerson method for determining the maximum flow in a flow network
• Serialization/Deserialization of a binary tree enables efficient tree reconstruction.
• The failure function of the Aho-Corasick pattern matcher is constructed.
• Graph bipartiteness evaluation
• We can use similar techniques to compute the transitive closure of a graph.