Untitled

from collections import deque

# Define the graph as an adjacency list
graph = {
    'S': ['A', 'B', 'C'],
    'A': ['D'],
    'B': ['E'],
    'C': ['F', 'S'],
    'D': ['G', 'H'],
    'E': ['I', 'J'],
    'F': [],
    'G': [],
    'H': [],
    'I': [],
    'J': []
}

# BFS function
def bfs(start, goal):
    # Initialize a queue for BFS and a set to track visited nodes
    queue = deque([start])
    visited = set([start])
    
    # To keep track of the path
    parent = {start: None}

    while queue:
        # Dequeue a node
        current_node = queue.popleft()
        
        # If we have reached the goal, reconstruct the path
        if current_node == goal:
            path = []
            while current_node:
                path.append(current_node)
                current_node = parent[current_node]
            return path[::-1]  # Return reversed path

        # Explore the neighbors of the current node
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current_node
                queue.append(neighbor)

    # If we finish the search without finding the goal
    return None

# Running the BFS function
start_state = 'S'
goal_state = 'J'
path = bfs(start_state, goal_state)

if path:
    print(f"Path from {start_state} to {goal_state}: {' -> '.join(path)}")
else:
    print(f"No path found from {start_state} to {goal_state}.")