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