Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. Here’s a simple implementation of BFS in Python, along with tracking the path traversed and finding the shortest path:

from collections import deque def bfs(graph, start, goal): # Using a queue to implement BFS queue = deque([(start, [start])]) # Set to keep track of visited nodes visited = set() while queue: current, path = queue.popleft() # Check if the current node is the goal if current == goal: return path # Return the path if the goal is reached # Check if the current node has been visited if current not in visited: visited.add(current) # Enqueue neighbors of the current node for neighbor in graph[current]: queue.append((neighbor, path + [neighbor])) return None # Return None if the goal is not reachable # Example graph represented as an adjacency list graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F', 'G'], 'D': ['B'], 'E': ['B', 'H'], 'F': ['C'], 'G': ['C'], 'H': ['E'] } start_node = 'A' goal_node = 'G' # Perform BFS and get the path result_path = bfs(graph, start_node, goal_node) # Print the path traversed and the shortest path if result_path: print(f"Path traversed: {result_path}") print(f"Shortest path from {start_node} to {goal_node}: {result_path}") else: print(f"No path found from {start_node} to {goal_node}")