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

- The
`dfs`

function performs the DFS traversal. It takes the graph, current node, visited array, and a list to store reachable nodes as inputs. - For each node visited during the DFS traversal, it is marked as visited and added to the list of reachable nodes.
- The function iterates through the neighbors of the current node and recursively explores unvisited neighbors.
- The
`find_reachable_nodes`

function initializes the visited array, then starts the DFS traversal from the given start node. - The program finally prints the list of reachable nodes.

## Leave a Review