#Chapter 47 bfs
#Breadth first search
GRAPH = {
    'A': {'colour': 'white', 'neighbours':['B','D','E']},
    'B': {'colour': 'white', 'neighbours':['A','D','C']},
    'C': {'colour': 'white', 'neighbours':['B','G']},
    'D': {'colour': 'white', 'neighbours':['A','B','E','F']},
    'E': {'colour': 'white', 'neighbours':['A','D']},
    'F': {'colour': 'white', 'neighbours':['D']},
    'G': {'colour': 'white', 'neighbours':['C']}  
    }

def bfs(vertex, graph):
    g = graph
    queue = []
    visitedNodes =[]
    queue.append(vertex)
    while len(queue) > 0:
        print('Queue is now', queue)
        print()
        currentNode = queue.pop(0)        
        print('Visiting', currentNode, '- setting it to black')
        g[currentNode]['colour'] = 'black'
        visitedNodes.append(currentNode)
        for n in g[currentNode]['neighbours']:
            print('  checking neighbour', n, '- colour is', g[currentNode]['colour'])
            if g[n]['colour'] is 'white':
                print('  appending neighbour', n, 'to queue and setting it to grey')
                queue.append(n)
                g[n]['colour'] = 'grey'
            # end if
        # end for
    # end while
    return visitedNodes
# end def bfs


print('Breadth first traversal of GRAPH starting at A','\n')
visited = bfs('A', GRAPH)
print('List of nodes visited: ',visited)