DFS.py

def dfs(graph, start, goal):
    stack = [start]
    visited = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)

            if node == goal:
                print("Goal found:", node)
                break

            
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    print("DFS Traversal:", visited)


graph = {}
nodes = int(input("Enter number of nodes: "))

for _ in range(nodes):
    node = input("Enter node: ").strip()
    neighbors = input(f"Enter neighbors of {node} (space-separated): ").split()
    graph[node] = neighbors

start = input("Enter start node: ").strip()
goal = input("Enter goal node: ").strip()


dfs(graph, start, goal)