bfs-tree.py

import collections

class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
    seen, queue = set([startnode]), collections.deque([startnode])
    while queue:
        vertex = queue.popleft()
        marked(vertex)
        for node in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append(node)

def marked(n):
    print(n)

tree = { "a" : set(["b","c"]),
                "b" : set(["e", "d"]),
                "c" : set(["f"]),
                "f" : set(["i"]),
                "e" : set(["g", "h"]),
                "d" : set(), "i" : set(), "g" : set(), "h" : set() 
                }

bfs(tree, "a")