BFS Graph Traversal

Graphs are one of the most important data structures in computer science. They represent networks of connections, whether it's social networks, web pages, city maps, or biological systems. However, to use graphs efficiently, we need good algorithms to explore and process them. For this purpose, graph traversal algorithms were introduced. Learn BFS Graph Traversal, a key algorithm that explores nodes level by level using a queue. Ideal for finding shortest paths in unweighted graphs and tree structures.

In this blog, we’ll explore what graph traversal is, why it matters, and delve into two of the most important traversal techniques: Depth-First Search (DFS) and Breadth-First Search (BFS). We’ll also touch upon more advanced topics like traversal in weighted graphs and applications in real-world scenarios.

What is Graph Traversal?

Graph traversal refers to the process of visiting each node (or vertex) in a graph in a systematic way. Depending on the traversal technique, the order in which nodes are visited may differ. Traversal helps us answer questions like:

• Is there a path between two nodes?
• Which is the shortest path available to travel from one node to another?
• Does the graph contain a cycle?
• What are the connected components?

Types of Graphs

Before we dive into the traversal techniques, it’s essential to understand the types of graphs:

• Directed vs Undirected Graphs: In directed graphs, each edge has a particular direction (A → B). In undirected graphs, edges are bidirectional.
• Weighted vs Unweighted Graphs: In weighted graphs, each edge has a weight. In unweighted graphs, all edges do not have any weight, and they are considered equal.
• Cyclic vs Acyclic Graphs: A cyclic graph contains at least one cycle. An acyclic graph does not have any cycles.
• Connected vs Disconnected Graphs: A connected graph has a path between every pair of nodes. A disconnected graph has at least one pair of nodes without a connecting path.

By knowing the graph type, it will help to choose the correct traversal algorithm.

Depth-First Search (DFS)

Concept:-

Depth-First Search is used to search each node in the graph depth-first. It uses a stack data structure, either explicitly or via recursion.

How it Works:-

1. Start at a node (source).
2. Mark the node as visited.
3. Recursively visit each unvisited neighbour.
4. Backtrack when no unvisited neighbours are left.

Code:-

def dfs(graph, start, visited=None):

    if visited is None:

        visited = set()

    visited.add(start)

    for neighbor in graph[start]:

        if the neighbor not in visited:

            dfs(graph, neighbor, visited)

    return visited

Use Cases:-

• Detecting cycles
• Solving mazes or puzzles
• Topological sorting
• Pathfinding in infinite graphs

Breadth-First Search (BFS)

Concept:-

Breadth-First Search explores all consecutive nodes from the current position before moving deeper. It uses a queue to manage the traversal order.

How it Works:-

1. Start at the source node.
2. Enqueue the node and mark it as visited.
3. Dequeue a node, process it, and enqueue its unvisited neighbours.
4. Repeat until the queue is empty.

Code:-

from collections import deque

def bfs(graph, start):

    visited = set()

    queue = deque([start])

    visited.add(start)

    while queue:

        node = queue.popleft()

        for neighbor in graph[node]:

            if neighbor not in visited:

                visited.add(neighbor)

                queue.append(neighbor)

    return visited

Use Cases:-

• Finding the shortest path in unweighted graphs
• Social networking (e.g., finding degrees of separation)
• Web crawling
• Network broadcasting

DFS vs BFS: A Comparison

Traversal in Weighted Graphs

DFS and BFS are ideal for unweighted graphs. When dealing with weighted graphs, especially for finding the shortest path, we need different algorithms:

Dijkstra's Algorithm

• Best for: Finding the Shortest path in the graphs where weights are positive.
• Approach: Greedily selects the nearest unvisited node.
• Time Complexity: The Time complexity for this algorithm is O((V + E) log V) with a priority queue.

A* Search

• Best for: Shortest path with a heuristic (e.g., in games).
• Approach: Uses a heuristic to guide traversal.
• Time Complexity: Depends on the heuristic.

Bellman-Ford Algorithm

• Best for: Graphs with negative weights.
• Time Complexity: O(VE)

These algorithms go beyond simple traversal and incorporate cost/weight analysis.

Applications of Graph Traversal

Graph traversal is not just a theoretical concept. It powers many real-world systems:

• Social Media: Finding mutual friends, suggesting connections (BFS).
• Search Engines: Crawling and indexing websites (BFS/DFS).
• Navigation Systems: Finding shortest paths (Dijkstra’s, A*).
• AI and Games: Pathfinding in game maps (DFS, A*).
• Compilers: Topological sorting using DFS for dependency resolution.
• Computer Networks: Broadcasting and routing information (BFS).

Graph Traversal Challenges

Despite their utility, graph traversal algorithms come with challenges:

• Infinite Graphs: May result in infinite loops if not handled correctly.
• Memory Constraints: BFS can consume a lot of memory on large graphs.
• Cycle Handling: Need to track visited nodes to avoid infinite loops.
• Disconnected Graphs: May require initiating traversal from multiple nodes.

Graph traversal is a foundational skill in computer science. Mastering DFS and BFS equips you to tackle a wide array of problems, from algorithm interviews to real-world system design. While these are the starting points, don’t stop there—learning about more complex traversal algorithms like Dijkstra's, A*, and Bellman-Ford will expand your ability to work with any graph structure.

In the world of interconnected systems, understanding how to explore a graph efficiently is more important than ever. Whether you’re a software engineer, data scientist, or hobbyist programmer, graph traversal will inevitably become a part of your toolkit.

Do visit our channel to explore more: SevenMentor

Author :- Sarika kore