search_graph = {
    's': ['a', 'd'],
    'a': ['b', 'c', 's'],
    'b': ['a', 'e', 'f', 'k'],
    'c': ['a'],
    'd': ['e', 'h', 's'],
    'e': ['b', 'd', 'k'],
    'f': ['b'],
    'g': ['k'],
    'h': ['d', 'i', 'j'],
    'i': ['h'],
    'j': ['h'],
    'k': ['b', 'e', 'g']
}
vertex = search_graph.keys()

open_list = ['s',]
closed_list = []
parent = {}
parent['s'] = None
while open_list:
    print open_list
    n = open_list.pop(0)
    #print n,
    closed_list.append(n)
    for m in search_graph[n]:
        if m not in closed_list:
            open_list.append(m)
            parent[m] = n
print parent
route = []
tb = 'g'
while tb:
    route.append(tb)
    tb = parent[tb]
route.reverse()
print route