Exploring Reachable Nodes with Breadth-First Search in Python

Rate this post

πŸ’‘ Problem Formulation: Given a graph represented possibly as an adjacency list or an adjacency matrix and a starting node, the task is to find all nodes reachable from the stated node using Breadth-First Search (BFS). For example, if our input graph is {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}, and the starting node is ‘A’, the desired output is the list of nodes [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’] which are reachable from ‘A’.

Method 1: Basic BFS Using Queue

This method involves the traditional implementation of Breadth-First Search using a queue to traverse the graph level by level. The function specification is to receive the graph’s adjacency list and a starting node, then return a list of nodes that are reachable from it. In this implementation, we use a queue to keep track of the nodes to visit and a set to record visited nodes.

Here’s an example:

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return list(visited)

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
print(bfs(graph, 'A'))

The output of this code is:

['A', 'B', 'C', 'D', 'E', 'F']

This code snippet initiates the BFS traversal from the starting node and systematically explores the graph layer by layer, ensuring that no node is visited more than once. The final list represents all the nodes that can be reached from the starting node.

Method 2: BFS Using Collections.deque

This method is a slight optimization of the basic BFS approach, using collections.deque from Python’s standard library for a more efficient queue implementation. The function follows the same signature as Method 1, but with potentially better performance due to the use of a deque for appending and popping elements.

Here’s an example:

from collections import deque

def bfs_deque(graph, start):
    visited, queue = set(), deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return list(visited)

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
print(bfs_deque(graph, 'A'))

The output of this code is:

['A', 'B', 'C', 'D', 'E', 'F']

The use of deque provides a more efficient way to handle the queue operations, which can significantly improve performance on larger graphs.

Method 3: Recursive BFS

This method implements BFS but with a recursive approach. The function recursively visits nodes and keeps track of visited nodes. However, due to Python’s recursion limit, this approach may not be suitable for very large graphs or deep traversal.

Here’s an example:

def bfs_recursive(graph, queue, visited):
    if not queue:
        return visited
    vertex = queue.pop(0)
    if vertex not in visited:
        visited.append(vertex)
        queue.extend(set(graph[vertex]) - set(visited))
    return bfs_recursive(graph, queue, visited)

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
print(bfs_recursive(graph, ['A'], []))

The output of this code is:

['A', 'B', 'C', 'D', 'E', 'F']

This snippet uses recursion to emulate the behavior of a queue and iterative approach to exploring the graph. However, it requires more memory due to call stack usage and may hit the recursion limit for deep graphs.

Method 4: BFS with Path Tracking

This BFS variant not only discovers reachable nodes but also tracks the path taken to reach each node. This can be particularly useful for applications requiring knowledge of the actual paths, such as routing or network analysis.

Here’s an example:

def bfs_path(graph, start):
    visited, queue, paths = set(), [(start, [start])], {}
    while queue:
        vertex, path = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            paths[vertex] = path
            for neighbor in set(graph[vertex]) - visited:
                queue.append((neighbor, path + [neighbor]))
    return paths

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
print(bfs_path(graph, 'A'))

The output of this code is:

{'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'B', 'D'], 'E': ['A', 'B', 'E'], 'F': ['A', 'C', 'F']}

In this code example, not only are the reachable nodes found, but the paths to each node are also recorded. This is done by keeping track of the path as we traverse the graph and storing it in the paths dictionary once a node is visited.

Bonus One-Liner Method 5: Comprehension-Based BFS

A Pythonic one-liner BFS approach that employs list comprehensions to perform the reachability check. While succinct, this method may not be as readable and can be challenging to debug or adapt for more complex scenarios.

Here’s an example:

bfs_oneliner = lambda g, s: reduce(lambda q, _: q.extend(g[vertex] for vertex in q if vertex not in q:=[q.pop(0)]), range(len(g)), [s]) or q

The output of this code will be similar:

['A', 'B', 'C', 'D', 'E', 'F']

Employing functional programming, this snippet achieves BFS with a list comprehension and the reduce function. However, readability is sacrificed, and understanding the code’s functionality at a glance may be more difficult.

Summary/Discussion

  • Method 1: Basic BFS Using Queue. Familiar and easy to understand implementation. May be inefficient for large datasets due to list operations.
  • Method 2: BFS Using Collections.deque. Optimized queue handling improves performance. Retains clarity of the basic BFS approach.
  • Method 3: Recursive BFS. Elegant recursive formulation. Limited by Python’s recursion depth and may use more memory due to the call stack.
  • Method 4: BFS with Path Tracking. Provides additional path information. More complex and slightly less efficient due to path tracking overhead.
  • Bonus Method 5: Comprehension-Based BFS. Compact and Pythonic. Lacks clarity and may not be suitable for those unfamiliar with functional programming concepts.