Learn Programming and technology with ease @ developerpublish.com

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

# Python Program to Find All Reachable Nodes in a Graph using DFS

This Python program utilizes Depth-First Search (DFS) to find all reachable nodes in a given graph. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

## Problem Statement

Given a graph represented as an adjacency list, write a program to find all the nodes that are reachable from a given starting node using Depth-First Search (DFS).

## Python Program to Find All Reachable Nodes in a Graph using DFS

```def dfs(graph, node, visited, reachable_nodes):
visited[node] = True
reachable_nodes.append(node)

for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited, reachable_nodes)

def find_reachable_nodes(graph, start_node):
num_nodes = len(graph)
visited = [False] * num_nodes
reachable_nodes = []

dfs(graph, start_node, visited, reachable_nodes)

return reachable_nodes

# Example graph represented as an adjacency list
graph = {
0: [1, 2],
1: [3],
2: [4],
3: [],
4: []
}

start_node = 0
reachable_nodes = find_reachable_nodes(graph, start_node)
print(f"Reachable nodes from node {start_node}: {reachable_nodes}")
```

## How It Works

1. The `dfs` function performs the DFS traversal. It takes the graph, current node, visited array, and a list to store reachable nodes as inputs.
2. For each node visited during the DFS traversal, it is marked as visited and added to the list of reachable nodes.
3. The function iterates through the neighbors of the current node and recursively explores unvisited neighbors.
4. The `find_reachable_nodes` function initializes the visited array, then starts the DFS traversal from the given start node.
5. The program finally prints the list of reachable nodes.

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