BFS Algorithm for Graph Traversal

BFS Algorithm for Graph Traversal

9 August 2023 0 By Anshul Pal

In this article we discuss the BFS Algorithm.Graphs form essential data structures for modeling relationships and connections between entities. They have applications in various domains, like computer networks, social networks, recommendation systems, and more. To efficiently navigate and analyze graphs, we use two important algorithms:

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS).

These algorithms offer distinct methods for traversing and exploring graphs, each with specific advantages and used cases. Let’s start our journey by understanding the BFS Algorithm or BFS Algorithm for Graph Traversal.

BFS Algorithm

BFS is abbreviated as Breadth First Search. It is an algorithm which helps us move through a graph step by step. It makes sure to visit all the nodes at one level before going to the next level. In simple words, it travels breadth wise and covers all the levels one by one according to its width. This way, we don’t miss any nodes at the same depth before moving to lower levels. BFS is really handy when we want to find the shortest path between two points in a graph without any weights on the connections. It’s like a guaranteed way to find the quickest path. BFS explores the nodes in a breadth-first order. BFS will explore all the nodes at a given distance from the source node before moving on to explore the nodes at the next distance.

Algorithm Steps

  1. Start at the initial node and enqueue it in a queue.
  2. While the queue is not empty, dequeue the front node and visit it.
  3. Enqueue all unvisited neighbors of the current node into the queue.
  4. Repeat steps 2 and 3 until the queue becomes empty.

Pseudocode for BFS Algorithm

BFS(graph, start_node):
create an empty queue
enqueue start_node into the queue
create a set to keep track of visited nodes
add start_node to the set of visited nodes

while the queue is not empty:
current_node = dequeue from the queue
process or visit current_node

for each neighbor_node of current_node:
if neighbor_node is not in the set of visited nodes:
add neighbor_node to the set of visited nodes
enqueue neighbor_node into the queue

In the above pseudocode graph represents the graph you are traversing and start_node is the node where you begins the traversal. The algorithm uses a queue to keep track of nodes to visit next and a set to keep track of visited nodes. It starts by enqueueing the starting node and marking it as visited. Then, it enters a loop where it dequeues the current node, processes it, and enqueues its unvisited neighbors. This process continues until the queue becomes empty, indicating that all nodes have been visited.

Python Code for BFS Algorithm

from collections import deque

def bfs(graph, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Initialize the queue with the starting node

while queue:
current_node = queue.popleft() # Dequeue the front node
if current_node not in visited:
print(current_node) # Process or visit the current node
visited.add(current_node) # Mark the current node as visited

# Enqueue unvisited neighbors
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)

# Example graph represented as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

start_node = 'A'
bfs(graph, start_node)

Output

PS C:\Users\itsan\OneDrive\Desktop\Python Tutorials> Python BFS.py
A
B
C
D
E
F

Thanks for reading. We hope that you like this post. If you have any queries related to this article, leave a comment down below!

Suggested Readings