Implémentons le parcours en profondeur python d’un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Introduction
Le principe et d’explorer le graphe à partir d’un sommet donné et on explore tous ses voisins en allant le plus profond possible (càd en répétant l’opération de sommet visité en sommet visité jusqu’à ce qu’on soit coincé, on revient alors via le chemin emprunté jusqu’au point de départ).
Le parcours en profondeur permet de trouver l’arbre couvrant du graphe qui n’est pas le même en général que l’arbre couvrant trouvé via le parcours en largeur du graphe.
L’algorithme en résumé :
Phase de descente :
Partir du sommet choisi pour démarrer et le marquer.
Tant que c’est possible :
- Aller vers un voisin non visité et le marquer.
- Mémoriser l’arrête ou l’arc par lequel on est passé.
- Si tous les voisins sont déjà visités :
- Revenir vers le sommet par lequel il a été découvert (backtrack phase : de remontée)
Si tous les sommets du graphe sont visités (sont dans l’arbre couvrant) alors le graphe est connexe sinon le graphe n’est pas connexe.
Exemple Python avec 3 graphes :
Module Python pour le parcours en profondeur :
#Parcours en profondeur d'un graphe
# Algorithme récursif : Le principe est d'explorer le graphe et de revenir sur ses pas lorsuqu'on est coincé.
def parcours_en_profondeur(graphe, sommet_en_cours:str, sommets_visites:[]):
print('Essai d explorer le sommet :' + str(sommet_en_cours))
if sommet_en_cours not in sommets_visites:
sommets_visites.append(sommet_en_cours) #Ajoute le sommet en cours au noeud visité
print('Exploration du sommet :' + str(sommet_en_cours))
sommets_voisins_non_visites = []
for sommet_voisin in graphe[sommet_en_cours]:
if sommet_voisin not in sommets_visites:
sommets_voisins_non_visites.append(sommet_voisin) # Constitue la liste des sommets voisins non encore visité
for sommet in sommets_voisins_non_visites:
#pour tout les sommets voisins non visités on effectue un parcours en profondeur
parcours_en_profondeur(graphe, sommet, sommets_visites)
#Fonction de test si le graphe est connexe suite à un parcours en profondeur
def est_un_graphe_connexe(graphe, sommets_visites):
if len(sommets_visites) == len(graphe):
print("Le graphe est connexe")
print(20 * "-")
else:
print("Le graphe n'est pas connexe")
print(20 * "-")
#Liste d'ajacence du graphe
graphe = {
'A': ['B','C'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C','A']
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#Exemple de graphe non connexe : Le sommet D n'est pas connecté au graphe
graphe = {
'A': ['B','C'],
'B': ['A','C'],
'C': ['A'],
'D': []
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#Autre exemple
graphe = {
'A': ['B','D'],
'B': ['A','C'],
'C': [],
'D': ['A']
}
sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)
#en fin de parcours si tout les sommets sont dans les sommets visités alors le graphe est connexe
#Note
#J'ai rencotré l'erreur IndentationError: unindent does not match any outer indentation level
#Je l'ai simplement résolu en reprenant toute l'indentation en debut de ligne
#et en la remplaçant par des Tabulation plutot que des espaces
https://128mots.com/index.php/category/non-classe/
Parcours en profondeur python : Liens externes :
https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
https://www.kartable.fr/ressources/mathematiques/cours/les-graphes/4795
http://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/graphe/1_notion_graphe.html