Breadth First Search (BFS) For a Graph

Intro to Breadth First Search
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring nodes at the current depth/distance from the target node before moving on to the nodes at the next depth level. This means that the algorithm visits all the nodes which are at a distance d from the target/root node before moving on to the nodes at a distance d+1.

The key characteristics of BFS algorithm are:

  • It explores all the neighboring nodes at the present depth before moving on to the next depth level.
  • Uses a queue data structure to keep track of the nodes to be visited.
  • Visits the nodes in the order they were added to the queue, following the First-In-First-Out (FIFO) principle.

Breadth First Search Algorithm

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring nodes at the present depth before moving on to the nodes at the next depth level. Here’s a step-by-step explanation of the BFS algorithm:

  1. Start with a graph and a starting node.
  2. Create a queue data structure to store the nodes to be visited.
  3. Use a set or an array to keep track of the nodes that have already been visited.
  4. Add the starting node to the queue and mark it as visited.
  5. While the queue is not empty:
    • Dequeue a node from the front of the queue.
    • Process the dequeued node (e.g., print it, perform some operation on it).
    • For each unvisited neighbor of the dequeued node, add it to the queue and mark it as visited.
  6. Repeat steps under step-5 until the queue is empty.

If you are new to queue data structure, you can learn more about it here.

Let’s now look at implementing the Breadth first search algorithm discussed in the previous section:


from collections import deque

def breadth_first_traversal(start_node, graph, visited):
  """
  Function to perform a Breadth First Search (BFS)
  starting from the start_node.
  
  Args:
  start_node: The node from which BFS starts.
  graph: The graph represented as an adjacency list.
  visited: A set to keep track of all visited nodes.
  """

  # Create a queue to store the nodes to be visited
  queue = deque()

  # Add the starting node to the queue and mark it as visited
  queue.append(start_node)
  visited.add(start_node)

  # Traverse the graph using BFS
  while queue:
    # Dequeue a node from the front of the queue
    current_node = queue.popleft()

    # Process the dequeued node (e.g., print it)
    print(current_node, end=' ')

    # Add all the unvisited neighbors of the dequeued node to the queue and mark them as visited
    for neighbor in graph[current_node]:
      if neighbor not in visited:
        queue.append(neighbor)
        visited.add(neighbor)

# Let's test BFS algorithm on the sample graph below
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

# Initialize an empty set to store all visited elements
visited = set()

# Perform breadth_first_traversal for each node in the graph
for node in graph:
  if node not in visited:
    # Start BFS at the current node
    breadth_first_traversal(node, graph, visited)

Time and Space Complexity

The time complexity of the basic BFS algorithm is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because the algorithm visits each node and edge at most once.

The space complexity of the basic BFS algorithm is O(V), as the algorithm needs to store all the neighboring nodes in the queue and the visited set or array. In worst case scenario, all nodes present in the graph might be neighbors to the root node and in this case all the V vertices will be added to the queue.

  • Finding the shortest path between two nodes: BFS is particularly useful for finding the shortest path between two nodes in a graph, as it explores all the neighboring nodes at the current depth before moving on to the next depth level, ensuring that the first time a node is visited, it is through the shortest path.
  • Breadth-first traversal: BFS can be used to traverse a graph, visiting all the nodes in the order they were added to the queue.
  • Level-order traversal of a tree: BFS can be used to perform a level-order traversal of a tree, where the nodes are visited level by level, from top to bottom.
  • Maze solving: BFS can be used to solve mazes by exploring all the possible paths from the starting point to the exit.

Overall, BFS is a powerful algorithm that is widely used in various applications, particularly when the goal is to find the shortest path or explore a graph in a systematic manner.