# Untitled

unknown

plain_text

9 days ago

1.5 kB

1

Indexable

Never

^{}

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}.")

Leave a Comment