DFS

def dfs_path(graph, start, goal, path=None, visited=None):

    # Initialize path and visited sets during the first call

    if path is None:

        path = [start]

    if visited is None:

        visited = set()

    visited.add(start)  # Mark the current node as visited

    # If the current node is the goal, return the path

    if start == goal:

        return path

    # Recursively visit all unvisited neighbors

    for neighbor in graph.get(start, []):

        if neighbor not in visited:

            new_path = dfs_path(graph, neighbor, goal, path + [neighbor], visited)

            if new_path:  # If a valid path is found, return it

                return new_path

    return None  # Return None if no path is found

# Example graph

graph = {

    'A': ['B', 'C'],

    'B': ['D', 'E'],

    'C': ['F', 'G'],

    'D': ['H'],

    'E': [],

    'F': ['I'],

    'G': [],

    'H': [],

    'I': []

}

# User input for start and goal nodes

start_node = input("Enter the start node: ").strip()

goal_node = input("Enter the goal node: ").strip()

# Validate if the nodes exist in the graph

if start_node not in graph or goal_node not in graph:

    print("Invalid start or goal node. Please ensure the nodes exist in the graph.")

else:

    # Find and display the path using DFS

    path = dfs_path(graph, start_node, goal_node)

    if path:

        print("Path from", start_node, "to", goal_node, ":", " -> ".join(path))

    else:

        print(f"No path exists between {start_node} and {goal_node}.")