G = dict()
G['a'] = ['b','c']
G['b'] = ['a','d','e']
G['c'] = ['a','d']
G['d'] = ['b','c','e']
G['e'] = ['b','d','f','g']
G['f'] = ['e','g']
G['g'] = ['e','f','h']
G['h'] = ['g']


def bfs(G, S):
	couleur = dict()
	for x in G :
		couleur[x] = 'blanc'
	P = dict()
	P[S] = None
	couleur[S] = 'gris'
	Q = [S]
	while Q :
		u = Q[0]
		for v in G[u]:
			if couleur[v] == 'blanc':
				P[v] = u
				couleur[v] = 'gris'
				Q.append(v)
		Q.pop(0)
		couleur[u] = 'noir'
	return P
	
	
	
P = bfs(G,'b')
print(P)