liste d 27adjacence python

1class Maillon:
2
3	def __init__(self, valeur, precedent=None, suivant=None):
4		self.valeur = valeur
5		self.precedent = precedent
6		self.suivant = suivant
7
8
9class File:
10
11	def __init__(self):
12		self.longueur = 0
13		self.debut = None
14		self.fin = None
15
16	def enfiler(self, valeur):
17		if self.longueur == 0:
18			self.debut = self.fin = Maillon(valeur)
19		else:
20			self.fin = Maillon(valeur, self.fin)
21			self.fin.precedent.suivant = self.fin
22		self.longueur += 1
23
24
25	def defiler(self):
26		if self.longueur > 0:
27			valeur = self.debut.valeur
28			if self.longueur > 1:
29				self.debut = self.debut.suivant
30				self.debut.precedent = None
31			else:
32				self.debut = self.fin = None
33			self.longueur -= 1
34		return valeur
35
36
37	def estVide(self):
38		return self.longueur == 0
39
40
41
42
43
44
45def bfs(G,s) :
46	P = {s :None}
47	Q = File()
48	Q.enfiler(s)
49	while not(Q.estVide()) :
50		u = Q.defiler()
51		for v in G[u] :
52			if v in P : continue
53			P[v]=u
54			Q.enfiler(v)
55	return P
56
57
58
59G = dict()
60G['a'] = ['b','c']
61G['b'] = ['a','d','e']
62G['c'] = ['a','d']
63G['d'] = ['b','c','e']
64G['e'] = ['b','d','f','g']
65G['f'] = ['e','g']
66G['g'] = ['e','f','h']
67G['h'] = ['g']
68
69
70P = bfs(G,'b')
71print(P)Copy