# BFS Algorithm for Graph Traversal

9 August 2023

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

- Start at the initial node and enqueue it in a queue.
- While the queue is not empty, dequeue the front node and visit it.
- Enqueue all unvisited neighbors of the current node into the queue.
- 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

*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.*

**start_node**## 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**

Hey there, I’m Anshul Pal, a tech blogger and Computer Science graduate. I’m passionate about exploring tech-related topics and sharing the knowledge I’ve acquired. With two years of industry expertise in blogging and content writing, I’m also the co-founder of HVM Smart Solution. Thanks for reading my blog – Happy Learning!