NSI Terminale
Si on se contente d'afficher l'étiquette des sommets :
def DFS_recursif(G, u, visites):
print(u) # "traiter" le sommet
for v in G[u]:
if v not in visites:
visites.append(v)
DFS_recursif(G, v, visites)
DFS_recursif(graphe, "A", ["A"])
On notera qu'au premier appel de la fonction, il faut penser à indquer que le sommet de départ à déjà été visité...
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 :
def DFS_recursif(G, u, visites):
for v in G[u]:
if v not in visites:
visites.append(v)
DFS_recursif(G, v, visites)
return visites
print(DFS_recursif(graphe, "A", ["A"]))
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"
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
from collections import deque
def cherche_circuit(G, depart)->dict:
"""
Parcourt un graphe depuis un de ses sommets afin de détecter un éventuel circuit.
Entrées :
G = le graphe ( orienté )
s = le sommet de départ du parcours
Sortie :
le dictionnaire des prédécesseurs de chaque sommet si un circuit est détecté, None sinon.
"""
pile = deque()
pred = {depart: None}
pile.append(depart)
while len(pile) != 0:
u = pile.pop()
for v in G[u] :
if v not in pred:
pred[v] = u
pile.append(v)
elif v == depart:
pred[v] = u
return pred
return None
def affiche_circuit(u, depart, pred:dict)->list:
"""
Renvoie un circuit sous la forme d'un tableau de sommets.
Entrées :
u = le sommet courant
depart = le sommet de départ du circuit
pred = le dictionnaire des prédécesseurs dans le circuit
Sortie :
tableau des sommets représentant le circuit
"""
if pred[u] == depart:
return [depart, u]
return affiche_circuit(pred[u], depart, pred) + [u]
def contient_circuit(G)->list:
"""
Recherche un circuit à partir de chacun des sommets du graphe, et l'affiche le cas échéant.
"""
for s in G:
res = cherche_circuit(G, s)
if res is not None:
return affiche_circuit(s, s, res) # reconstruction du circuit depuis le sommet...jusqu'à lui-même
return None
from collections import deque
def cherche_cycle(G, depart)->dict:
"""
Parcourt un graphe depuis un de ses sommets afin de détecter un éventuel cycle.
Entrées :
G = le graphe
depart = le sommet le sommet de départ
Sortie :
le dictionnaire des prédécesseurs de chaque sommet si un cycle est détecté, None sinon.
"""
pile = deque()
pred = {depart: None}
pile.append((depart, None))
while len(pile) != 0:
u, p = pile.pop()
for v in G[u] :
if v not in pred:
pred[v] = u
pile.append((v, u))
elif p != v:
pred[v] = u
return pred
return None
def affiche_cycle(u, depart, pred:dict)->list:
"""
Renvoie un cycle sous la forme d'un tableau de sommets
Entrées :
u = le sommet courant
depart = le sommet de départ du cycle
pred = le dictionnaire des prédécesseurs dans le cycle
Sortie :
tableau des sommets représentant le cycle
"""
if pred[u] == depart:
return [u, depart]
return affiche_cycle(pred[u], depart, pred) + [u]
def contient_cycle(G):
"""
Recherche un cycle à partir de chacun des sommets d'un graphe non-orienté, et l'affiche le cas échéant.
"""
for s in G:
res = cherche_cycle(G, s)
if res is not None:
return affiche_cycle(s, s, res) # reconstruction du circuit depuis le sommet...jusqu'à lui-même
return None
def distances(G: Graphe, r: str)->dict:
d = {sommet: inf for sommet in G.graphe} # initialisation du dictionnaire des distances
file = deque()
file.append(r)
d[r] = 0 # distance de la racine à elle-même = 0 !
while len(file) != 0:
u = file.popleft()
for v in G.adjacents_de(u):
if d[v] == inf:
file.append(v)
d[v] = d[u] + 1
return d