Learn Programming and technology with ease @ developerpublish.com

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

# 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)

self.graph[u].append(v)

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

queue.append(start)

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

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

return reachable_nodes

def main():
graph = Graph()

# Add edges to the graph (example)

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

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...