Find shortest path in an unweighted undirected graph using BFS

bfs_shortest_path.py

# Simple bfs implementation to explore a graph.
# An undirected graph as an adjancency representation.


from collections import deque

G = {0: (1, 2), 1: (0, 6), 6: (1, 3), 3: (2, 4, 6), 5: (2, ), 2: (5, 0, 3), 4: (3, )}
source = 6
end = 2


def bfs_shortest_path(start, end, G):
    queue = deque([(start, [start])])
    # list of visited nodes
    visited = [start]
    # while there is something to explore, we look for the children
    # and append these to the queue and mark them as visited.
    if start == end:
        print("Start is the end, so no path needed!")

    while queue:
        node, path = queue.popleft()
        if node == end:
            print(f"Shortest path from start {start} to end {end}", path)
            return path
        for child in G[node]:
            if child not in visited:
                queue.append((child, path + [child]))
                visited.append(child)
    # No path was found.
    print("No path is found")
    print("Order of visit", visited)
    return None

shortest_path = bfs_shortest_path(source, end, G)