NSI Terminale
Si on se contente d'afficher l'étiquette des sommets :
def DFS_recursif(G, u, visites):
print(u) # "traiter" le sommet
visites.append(u)
for v in G[u]:
if v not in visites:
DFS_recursif(G, v, visites)
DFS_recursif(graphe, "A", [])
Si on veut renvoyer le tableau des sommets dans l'ordre de leur parcours, il suffit de renvoyer le tableau visites en fin de parcours :
Si on utilise une deque, on peut utiliser le côté "gauche" ou "droit" comme sommet de pile, c'est aussi efficace...
from collections import deque
def DFS_iteratif(G, s):
pile = deque()
visites = [s] # penser à marquer le sommet de départ comme déjà visité
pile.append(s) # on utilise ici le côté "droit" pour le sommet de la pile
while len(pile) != 0:
u = pile.pop()
for v in G[u] :
if v not in visites:
visites.append(v)
pile.append(v)
return visites
print(DFS_iteratif(graphe, "A"))
On remplace simplement la pile par une file 😎 :
from collections import deque
def BFS(G, s):
file = deque()
visites = [s]
file.append(s) # queue = côté "droit"
while len(file) != 0:
u = file.popleft() # tête = côté "gauche"
for v in G[u] :
if v not in visites:
visites.append(v)
file.append(v)
return visites
print(BFS(graphe, "A"))
from collections import deque
def cherche_chemin(G, depart, fin):
pile = deque()
pred = {depart: None} # Ne pas oublier !
pile.append(depart)
while len(pile) != 0:
u = pile.pop()
for v in G[u]:
if v not in pred: # si v n'est pas dans le dictionnaire 'pred', c'est qu'il n'a pas encore été visité
pred[v] = u # u est le prédécesseur direct de v dans le chemin
pile.append(v)
if fin in pred: # si le chemin existe
return pred
else:
return None # 'fin' n'est pas dans le dictionnaire, c'est qu'on ne l'a pas visité -> pas de chemin entre 'fin' et 'debut'
On peut améliorer l'efficacité de la recherche en l'arrêtant à partir du moment où, au cours du parcours, on a rencontré le sommet d'arrivée, et sortir alors de la fonction en renvoyant le dictionnaire pred
Inconvénient : on n'a alors pas tous les chemins depuis le sommet de départ vers chacun des sommets accessibles, uniquement vers le sommet de fin...
from collections import deque
def cherche_chemin(G, depart, fin):
pile = deque()
pred = {depart: None} # Ne pas oublier !
pile.append(depart)
while len(pile) != 0:
u = pile.pop()
if u == fin: # on a rencontré, au cours du parcours, le sommet de fin
return pred # on arrête la recherche, le chemin est trouvé...
for v in G[u]:
if v not in pred:
pred[v] = u
pile.append(v)
return None # on a parcouru tout le graphe sans rencontrer le sommet 'fin' : pas de chemin !
def chemin(s, pred: dict)->list:
if pred[s] == None: # Cas de base : on est "remonté" jusqu'au sommet de départ ?
return [s] # alors on le renvoie.
else : # Cas général :
return chemin(pred[s], pred) + [s] # chemin jusqu'à s = chemin jusqu'au prédécesseur de s + s
def chemin(s, pred: dict)->str:
chemin = [s]
while pred[s] != None:
s = pred[s]
chemin = [s] + chemin
return chemin
Utilisation d'un parcours BFS :
def plus_court_chemin(G, debut, fin)->dict:
file = deque()
pred = {debut: None}
file.append(debut)
while len(file) != 0:
u = file.popleft()
if u == fin:
return pred
for v in G[u]:
if v not in pred:
pred[v] = u
file.append(v)
return None