Python Program to Find All Reachable Nodes in a Graph using BFS

In this Python program, we will use Breadth-First Search (BFS) to find all reachable nodes in a graph starting from a given source node. BFS is a widely used graph traversal algorithm that explores all the neighbors of a node before moving to their children, making it perfect for finding reachable nodes from a starting point.

Problem Statement

Given a graph represented as an adjacency list and a source node, we need to find all the nodes that are reachable from the source node using BFS.

Python Program to Find All Reachable Nodes in a Graph using BFS

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, start):
        visited = set()
        queue = []
        reachable_nodes = []

        visited.add(start)
        queue.append(start)

        while queue:
            node = queue.pop(0)
            reachable_nodes.append(node)

            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return reachable_nodes

def main():
    graph = Graph()

    # Add edges to the graph (example)
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(1, 2)
    graph.add_edge(2, 0)
    graph.add_edge(2, 3)
    graph.add_edge(3, 3)

    source_node = 2  # Change this to your desired source node

    reachable_nodes = graph.bfs(source_node)

    print(f"Nodes reachable from node {source_node}:")
    for node in reachable_nodes:
        print(node, end=" ")
    print()

if __name__ == "__main__":
    main()

How it Works

  1. We define a Graph class to represent the graph using an adjacency list.
  2. The add_edge method is used to add edges to the graph.
  3. The bfs method performs a BFS traversal starting from the given source node. It uses a queue to keep track of nodes to be visited.
  4. We maintain a visited set to ensure that we don’t visit a node multiple times.
  5. The reachable nodes are stored in the reachable_nodes list and returned as the result.

Input/Output

Python Program to Find All Reachable Nodes in a Graph using BFS

Leave A Reply

Your email address will not be published. Required fields are marked *

You May Also Like

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...
This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...
This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...