#!/usr/bin/env python
# Breadth-First Search in Python
from collections import deque

class Node:
    def __init__(self, identifier):
        self.identifier = identifier
        self.adjacencies = []
        self.marked = False

    def addArrayOfAdjacencies(self, adj_list):
        for adjacency in adj_list:
            self.adjacencies.append(adjacency)

node_a = Node('a')
node_b = Node('b')
node_c = Node('c')
node_d = Node('d')
node_e = Node('e')
node_f = Node('f')

node_a.addArrayOfAdjacencies([node_b, node_c, node_d])
node_b.addArrayOfAdjacencies([node_a, node_e, node_f])
node_c.addArrayOfAdjacencies([node_a, node_f])
node_d.addArrayOfAdjacencies([node_a])
node_e.addArrayOfAdjacencies([node_b])
node_f.addArrayOfAdjacencies([node_b, node_c])

def bfs(source):
    queue = deque([])
    result = []
    queue.append(source)
    source.marked = True
    result.append(source)
    while not len(queue) == 0:
        v = queue.popleft()
        for adjacency in v.adjacencies:
            if not adjacency.marked:
                adjacency.marked = True
                result.append(adjacency)
                queue.append(adjacency)
    return result

bfs_result = bfs(node_a)
for node in bfs_result:
    print node.identifier