Breadth-First-Search (BFS) in Python for Path Traversed and Shortest Path Taken

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

In this example, the graph represents an undirected graph using an adjacency list. The bfs function takes the graph, start node, and goal node as inputs and returns the path traversed as well as the shortest path from the start to the goal node. The algorithm uses a queue to explore nodes in a breadth-first manner, and the visited set helps prevent revisiting nodes.

Leave a Reply

Your email address will not be published. Required fields are marked *