Breadth First Search of a Graph

bfs.py

#https://docs.python.org/2/tutorial/datastructures.html
from collections import deque

def bfs(g, root_node):
    """ Implementation of a breadth first search (BFS)
    BFS is useful e.g. when we need to find a route between 
    It is NOT recursive
    
    Algo:
    1. Enqueue root node;
    2. While queue is not empty:
        (a) extract element from a queue;
        (c) for all neighbours: if they are not marked as visited, enqueu them and mark as visited.
    3. return visited
    
    Parameters
    ----------
    g: dict
        dictionary with nodes and corresponding neighbors
    
    Returns
    -------
    visited: set
        set of visited nodes
    """
    
    if len(g)==0:
        return
    
    q = deque([])
    visited = [] #set()
    q.append(root_node)
    visited.append(root_node)
    
    while len(q)!=0:
        curr_node = q.popleft()
        for neigh_node in g[curr_node]:
            if neigh_node not in visited:
                visited.append(neigh_node)
                q.append(neigh_node)
                
    return visited


g = {0:[8, 1, 3, 4], 1:[0,2, 5], 2:[1, 3], 3:[0, 2, 4], 4:[0, 3], 5:[1], 8:[0]}
bfs(g, root_node=2)

g = {}
bfs(g, root_node=2)