Tag: bfs

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