3-03. Parcours de graphes

• Parcourir un graphe en largeur
• Chercher un chemin dans un graphe

Principe de l’algorithme

1. Le parcours en largeur est l'un des algorithmes de parcours les plus simples. Il est à la base de nombreux algorithmes importants sur les graphes comme la recherche du plus court chemin ou la détection de composantes connexes.

Étant donné un graphe $*G*$, orienté ou non, et un sommet $*s*$, le parcours en largeur découvre tout d’abord les sommets à distance 1 de $*s*$, puis ceux à distance 2, puis ceux à distance 3, etc. jusqu’à avoir découvert tous les sommets de $*G*$ accessibles depuis $*s*$.

L’algo construit ainsi un arbre de parcours en largeur de racine $*s*$ donnant, pour chaque sommet $*u*$ accessible depuis $*s*$, un « plus court chemin » de $*s*$ à $*u*$ dans $*G*$, c’est-à-dire un chemin contenant le plus petit nombre de connexions. Bien sûr, le parcours obtenu en sortie est différent selon le sommet de départ, mais aussi selon l’ordre dans lequel les sommets adjacents à un sommet donné sont visités.

Structures de données

L’algorithme utilise plusieurs attributs pour les sommets u du graphe :

• u.couleur qui permet de stocker les valeurs blanc (inexploré), gris (en cours d’exploration) ou noir (exploration terminée) ;
• u.pere (optionnel) qui permet de stocker le prédécesseur de u dans le parcours afin de construire l’arbre de parcours ;
• u.distance (optionnel) qui permet de stocker la distance depuis le sommet s dans le parcours.

Les attributs optionnels ne sont pas nécessaires pour le bon déroulement de l’algorithme. Mais ils permettent de stocker des informations qui peuvent être exploitées ensuite si on souhaite tracer l’arbre de parcours.

L’algorithme utilise également une file (FIFO – First In First Out) pour gérer les sommets gris : un sommet est mis dans la file dès qu’il est colorié en gris, il y reste tant qu’il a des successeurs encore blancs et en sort lorsqu’il est colorié en noir.

Algorithme formel

Voici l’algorithme le plus simple permettant le parcours en largeur d’un graphe. Il utilise une file, notée F

		ParcoursLargeur(Graphe G, Sommet s):
			F.enfiler(s)
			marquer s;
			tant que la file n’est pas vide
			|	u ← F.defiler() # on retire le premier sommet de la file
			|	pour tout voisin v de u
			|	|	si v non marqué
			|	|	|	F.enfiler(v);
			|	|	|	marquer v;
	

Voici un algorithme plus élaboré de parcours en largeur, permettant d’exploiter ce parcours pour en tirer des informations.

		def parcours_en_largeur(G, sommet_depart)

			# On initialise le sommet de départ
			sommet_depart.couleur ← gris
			sommet_depart.pere ← null
			sommet_depart.distance ← 0

			# On initialise tous les autres sommets du graphe
			pour chaque sommet de G autre que sommet_depart :
			|	sommet.couleur ← blanc
			|	sommet.pere ← null
			|	sommet.distance ← null

			# On initialise la file F
			F ← {sommet_depart}

			tant que F n’est pas vide :
			|	sommet_visite ← F[1] # on prend le premier sommet de la file
			|	F ← F - {sommet_visite}  # et on le retire de la file
			|	pour chaque voisin de sommet_visite :
			|	| 	si voisin.couleur = blanc alors # il s’agit d’un sommet inexploré
			|	| 	|	voisin.couleur ← gris # on le marque comme en cours d’exploration
			|	| 	|	voisin.pere ← sommet_visite
			|	| 	|	voisin.distance ← sommet_visite.distance + 1
			|	| 	|	F.ajouter(voisin) # on l’ajoute à la file
			|	sommet_visite.couleur ← noir # tous les voisins ont été explorés

			renvoyer les sommets visités du graphe
	

La complexité de l’algorithme est en $*O(\mathrm{card}(S)+\mathrm{card}(A))*$ pour une implémentation par listes d’adjacences et en $*O(\mathrm{card}(S)^2)*$ pour une implémentation par matrice d’adjacence.

Si le graphe n’est pas connexe, ce parcours ne va pas couvrir tous les sommets du graphe. Si on souhaite parcourir tous les sommets, il faudra vérifier s’il reste des sommets en blanc et relancer l’algorithme sur ces sommets.

On obtient alors une forêt d’arbres de parcours en largeur. Si le graphe est connexe (ou fortement connexe dans le cas d’un graphe orienté), on n’a bien sûr qu’un seul arbre.

Illustration du fonctionnement de l’algorithme

La suite de schémas ci-dessous illustre le déroulement de l’algorithme de parcours en largeur.

Sur chaque sommet figure le couple (prédécesseur, distance au sommet de départ) en l’état actuel d’exécution de l’algo. Le signe ⊗ symbolise l’absence de prédécesseur. Lorsque la distance n’a pas encore été calculée, sa valeur est infinie (∞).

Arbre de parcours en largeur

La relation père/fils établie entre les différents sommets lors de l’algorithme du parcours en largeur permet de définir une relation hiérarchique entre les sommets accessibles depuis le sommet initial $*s*$. Les branches de l’arbre suivies depuis $*s*$ jusqu’à un sommet $*u*$ fournissent un plus court chemin de $*s*$ à $*u*$. Ce chemin est simple, c’est-à-dire qu’il ne passe que par des sommets distincts. Bien sûr, cet arbre de parcours dépend du sommet de départ, mais aussi de l’ordre dans lequel les sommets adjacents à un sommet donné sont visités.

L’arbre de parcours en largeur permet d’établir de nombreux résultats sur la structure du graphe. Par exemple, il permet de déterminer :

• si un graphe non orienté est connexe et, s’il ne l’est pas, de déterminer ses composantes connexes ;
• tous les sommets accessibles depuis un sommet donné ;
• tous les sommets situés à une certaine distance d’un sommet donné ;
• un plus court chemin entre deux sommets donnés du graphe, s’il existe et si les arêtes ne sont pas valuées.

Parcours en largeur

On considère les graphes suivants :

1. Représenter ces graphes par des listes d’adjacences dans lesquelles les sommets sont listés par valeurs décroissantes.

2. Appliquer l’algorithme du parcours en largeur à cette représentation en partant du sommet 7 pour le graphe (a) et du sommet 8 pour le graphe (b). Quels sont les arbres de parcours obtenu ?

3. Suivant l’arbre obtenu pour le graphe (a), quel est le plus court chemin entre le sommet 7 et le sommet 3 ?

4. Suivant l’arbre obtenu pour le graphe (b), que peut-on dire sur la forte connexité du graphe ?

Implémentation du parcours en largeur

On considère l'implémentation incomplète suivante du parcours en largeur :

			def creer_parcours_largeur(graphe, sommet_depart):
				'''
				graphe : donné par un dictionnaire de ses listes d'adjacences
				sommet_depart : un sommet du graphe
				renvoie le parcours sous forme de dictionnaire dont les clés
				sont les sommets du graphe explorés et dont les valeurs associées sont
				des dictionnaires avec les clés "couleur", "parent", "distance"
				'''

				parcours = {}
				parcours[sommet_depart] = {"couleur": "gris", "parent": None, "distance": 0}
				for sommet in graphe :
					if sommet ... :
						parcours[sommet] = {"couleur": ..., "parent": ..., "distance": None}
				
				file = [sommet_depart]
				while file != ...:
					sommet_visite = ...
					for voisin in ... :
						if parcours[voisin]["couleur"] == ... :
							parcours[voisin]["couleur"] = ...
							parcours[voisin]["parent"] = ...
							parcours[voisin]["distance"] = ...
							file.append(...)
					parcours[sommet_visite]["couleur"] = ...
				return { sommet: details for sommet, details
					in parcours.items() if details["couleur"] == "noir" }
		

1. La variable parcours est un dictionnaire dont les clés sont les sommets du graphe et dont les valeurs associées sont des dictionnaires avec les clés couleur, parent et distance de l'algorithme du parcours en largeur. Compléter les lignes 13 et 14 permettant d'initialiser le contenu de cette variable.

2. Compléter le reste de la fonction.

3. Quelle est la différence entre le dictionnaire renvoyé par la fonction et le dictionnaire parcours ?

4. Tester votre code avec les deux graphes donnés dans l’exercice précédent. Vérifiez que les résultats sont bien cohérents avec ceux obtenus à la main dans l'exercice précédent.

Informations structurelles

Le but de cet exercice est de proposer quatre applications simples du parcours en largeur à la recherche d'informations structurelles sur un graphe représenté par des listes d'adjacences.

On testera les fonctions sur les graphes de l’exercice « Parcours en largeur ».

1. Connexité. On considère ici un graphe non orienté.

1.1. Comment vérifier la connexité de graphe grâce à l’arbre de parcours en largeur obtenu à partir d'un sommet quelconque ?

1.2 En déduire le code de la fonction est_connexe ci-dessous qui prend en paramètre un graphe non orienté et renvoie un booléen. Tester la fonction sur le graphe (a).

			def est_connexe(graphe):
				# on récupère le premier sommet quelle que soit sa clé
				premier_sommet = next(iter(graphe))
				parcours_largeur = ...
				return ...
		

2. Chemins. Compléter la fonction est_accessible ci-dessous qui détermine s’il existe un chemin entre sommet1 et sommet2 d’un graphe, orienté ou non. Elle renvoie un booléen. Tester la fonction sur les deux graphes (a) et (b).

			def est_accessible(graphe, sommet1, sommet2):
				assert sommet1 in graphe and sommet2 in graphe, \
					'{0} et {1} doivent être des sommets de G'.format(sommet1, sommet2)
				parcours_largeur = ...
				return ...
		

3. Distance. La fonction get_sommets_a_distance ci-dessous prend en paramètre un graphe orienté ou non, un sommet et une distance (qui doit être de type int), et renvoie un tuple, éventuellement vide, donnant tous les sommets du graphe accessibles depuis le sommet donné et la distance donnée.

			def get_sommets_a_distance(graphe, sommet, distance):
				assert ..., '{0} doit être un sommet de {1}'.format(sommet, graphe)
				assert isinstance(distance, int) and distance >= 0, 'la distance doit être un entier naturel'
				parcours_largeur = ...
				return tuple(s for ... if ...)
		

4. Plus court chemin. Compléter la fonction get_plus_court_chemin ci-dessous prenant en paramètre un graphe et deux sommets, et renvoyant un tuple donnant un chemin le plus court reliant sommet1 à sommet2.

			def recherche_plus_court_chemin(parcours_largeur:dict, sommet1, sommet2, sommets_chemin:tuple):
				'''
				Fonction récursive parcourant l'arbre de parcours dans le sens sommet2 → sommet1
				pour construire le plus court chemin entre sommet1 et sommet2
				L'arbre de parcours est le dictionnaire obtenu par get_parcours_largeur
				'''
				if sommet1 == sommet2: return (sommet1,) + sommets_chemin
				sommets_chemin = (sommet2,) + sommets_chemin
				predecesseur_sommet2 = parcours_largeur[sommet2][0]
				return recherche_plus_court_chemin(..., ..., ..., ...)


			def get_plus_court_chemin(graphe, sommet1, sommet2):
				'''
				graphe orienté ou non, donné par un dictionnaire de ses listes d'adjacences
				sommet1 et sommet2 sont deux sommets du graphe
				Renvoie un tuple donnant un chemin le plus court allant de sommet1 à sommet2
				si sommet2 est accessible depuis sommet1 et un tuple vide sinon.
				'''
				assert ..., 'Les sommets doivent être dans le graphe'
				parcours_largeur = get_parcours_largeur(graphe, sommet1)
				if sommet2 not in parcours_largeur: return ...
				return recherche_plus_court_chemin(parcours_largeur, sommet1, sommet2, ())
		

• Parcourir un graphe en profondeur
• Repérer la présence d’un cycle dans un graphe

Principe de l’algorithme

La stratégie suivie par un parcours en profondeur est, comme son nom l’indique, de descendre « plus profondément » dans le graphe chaque fois que c’est possible.

Lors d’un parcours en profondeur, les connexions sont systématiquement explorées à partir du sommet $*u*$ découvert le plus récemment et dont on n’a pas encore exploré tous les connexions qui en partent. Lorsque toutes les connexions qui partent de $*u*$ ont été explorées, l’algorithme « revient en arrière » pour explorer les connexions qui partent du sommet à partir duquel $*u*$ a été découvert. Ce processus se répète jusqu’à ce que tous les sommets accessibles à partir d’un sommet source initial aient été découverts.

Structure de données

L’algorithme utilise plusieurs attributs pour les sommets u du graphe :

• u.couleur qui permet de stocker les valeurs blanc (inexploré), gris (en cours d’exploration) ou noir (exploration terminée) ;
• u.pere (optionnel) qui permet de stocker le prédécesseur de u dans le parcours afin de construire l’arbre de parcours ;
• u.debut (optionnel) qui permet de stocker la « date » à laquelle le sommet u a été découvert ;
• u.fin (optionnel) qui permet de stocker la date à laquelle le parcours a fini d’examiner la liste d’adjacence de u.

L’algorithme utilise implicitement une pile (LIFO – Last In First Out), via la récursion, pour gérer l’ordre d’exploration des sommets.

Algorithme formel

Voici l’algorithme le plus simple possible permettant le parcours en profondeur d’un graphe G à partir d’un sommet de départ s :

Durant l'exploration, on marque les sommets afin d'éviter de re-parcourir des sommets parcourus. Initialement, aucun sommet n'est marqué.

		explorer(graphe G, sommet s)
			marquer s
			pour tout sommet v voisin de s
			|		si v n'est pas marqué alors
			|		|	explorer(G, v)
	

Voici un algorithme un peu plus développé qui va permettre d’exploiter le parcours en profondeur pour en tirer des renseignements

		parcours_profondeur (g, sommet_depart)
			# On initialise tous les sommets du graphe g
			pour chaque sommet de g :
			|	sommet.couleur ← blanc
			|	sommet.pere ← null
			|	sommet.debut ← ∞
			|	sommet.fin ← ∞

			# On initialise la date
			date ← 0

			# On lance la fonction "visiter" qui est récursive
			visiter(sommet_depart)

		visiter(sommet):
		|	date ← date + 1 # date est une variable globale
		|	sommet.couleur ← gris
		|	sommet.debut ← date
		|	pour chaque voisin de sommet:
		|	|	si voisin.couleur = blanc:
		|	|	|	voisin.pere = sommet
		|	|	|	visiter(voisin)
		|	sommet.couleur ← noir
		|	date ← date + 1
		|	sommet.fin ← date

	

La complexité de l’algorithme est en $*O(\mathrm{card}(S)+\mathrm{card}(A))*$ pour une implémentation par listes d’adjacences et en $*O(\mathrm{card}(S)^2)*$ pour une implémentation par matrice d’adjacence.

Là encore, si le graphe n’est pas (fortement) connexe, il faudra relancer l’algo sur les sommets restés inexplorés, jusu’à ce que tous les sommets aient été visités.

Illustration du fonctionnement de l’algorithme

La suite de schémas ci-dessous illustre le déroulement de l’algorithme de parcours en profondeur. Les sommets sont pris dans l’ordre alphabétique lorsqu’un choix doit être fait. Chaque sommet est marqué par le triplet (prédécesseur, date de découverte, date de fin d’exploration)

Arbre de parcours en profondeur

Connexions du graphe et branche des arbres de parcours

Lors du parcours, certaines connexions (arc ou arête) peuvent ne jamais être parcourues par l’algo. On peut classer les connexions du graphe en quatre catégories :

• Connexion de liaison ou connexion d’arbre : ce sont les connexions du graphe présentes dans l’arbre de parcours.
  Par exemple, l’arête (a,b) est une arête de liaison.
• Connexion arrière : ce sont des connexions du graphe qui, sur l’arbre de parcours, connectent un sommet $*u*$ à un ancêtre $*v*$.
  Par exemple, l’arête (a,e) connecte le sommet e à son ancêtre sur l’arbre, le sommet a.
• Arc avant : dans le cas d’un graphe orienté, c’est un arc reliant un sommet à un descendant sur l’arbre, sans être un arc de liaison. Dans un graphe non orienté, il n’y a pas de distinction entre arête avant et arête arrière, car les arêtes ne sont pas orientées. On les appelle toutes arêtes arrières.
• Connexions transverses : ce sont des connexions du graphe qui n’appartiennent pas à une des catégories précédentes. Elles peuvent relier deux sommets d’un même arbre de parcours du moment que l’un des sommets ne soit pas un ancêtre de l’autre, ou deux sommets de deux arbres de parcours différents.

Parcours en profondeur

On reprend les graphes des exercices précédents, ainsi que leur listes d’adjacence.

graphe_a = { 1: [7, 6, 5, 4], 2: [7, 4], 3: [6, 5], 4: [7, 5, 2, 1], 5: [6, 4, 3, 1], 6: [5, 3, 1], 7: [4, 2, 1] }
graphe_b = { 1: [7], 2: [6, 5], 3: [1], 4: [1], 5: [8, 3], 6: [5, 2], 7: [4, 3], 8: [7, 3] }

1. Appliquer l’algorithme du parcours en profondeur à chacun de ces graphes, autant de fois que nécessaire pour que tous les sommets soient visités. Commencer par le sommet 1.

2. Quelles sont les forêts de parcours obtenues ? On classifiera également les connexions selon leur type.

Parcours en profondeur – implémentation

On reprend les graphes des exercices précédents, ainsi que leur listes d’adjacence.

graphe_a = { 1: [7, 6, 5, 4], 2: [7, 4], 3: [6, 5], 4: [7, 5, 2, 1], 5: [6, 4, 3, 1], 6: [5, 3, 1], 7: [4, 2, 1] }
graphe_b = { 1: [7], 2: [6, 5], 3: [1], 4: [1], 5: [8, 3], 6: [5, 2], 7: [4, 3], 8: [7, 3] }

1. Compléter la fonctions visiter ci-dessous en vous aidant de l’algorithme formel vu dans cette partie.

			def visiter(graphe, parcours, sommet, date):
				# ...
				# ...
				# ...
				for voisin in ...:
					if parcours[voisin]["couleur"] == ...:
							# ...
							parcours, date = visiter(graphe, parcours, ..., date)
				# ...
				# ...
				# ...
				return parcours, date


			def creer_parcours_profondeur(graphe, sommet_depart):
				'''
				graphe donné par un dictionnaire représentant ses listes d'adjacences
				Renvoie un dictionnaire dont les clés sont les sommets de graphe et dont les valeurs
				associées sont des dictionnaires avec les clés suivantes:
				- "couleur" indique le statut d’exploration (blanc, gris ou noir)
				- "parent" indique le parent de la clé,
				- "date_debut" indique la date où la clé a été découverte la première fois et où
				- "date_fin" indique la date où le parcours a fini d'examiner la liste d'adjacence de la clé
				'''
				parcours = {}
				for sommet in graphe:
					parcours[sommet] = {"couleur": "blanc", "parent": None, "date_debut": None, "date_fin": None}
				date = 0
				parcours, date = visiter(graphe, parcours, sommet_depart, date)
				return { sommet: details for sommet, details in parcours.items() if details["couleur"] == "noir" }
		

2. Tester la fonction creer_parcours_profondeur sur les deux graphes.

3. Pourquoi les résultats fournis par cette fonction sur le graphe (b) ne correspondent-ils pas exactement aux résultats trouvés à l’exercice précédent ?

Détection de cycle

On s’intéressera ici aux cycles de longueur 2 ou plus, autrement dit, on ne s’interesse pas à une connexion qui part d’un sommet et revient à ce même sommet.

On rappelle qu’un cycle est un chemin simple (passant par des connexions toutes différentes) et fermé (on revient au sommet de départ). Cela signifie que pour détecter un cycle de longueur ≥ 2, il faut que l’algorithme découvre un sommet déjà visité en passant par une connexion qui n’a pas encore été parcourue.

Dans un graphe non orienté

Voici l’algorithme de détection des cycles pour un graphe non orienté :

		explorer_cycle(graphe g, sommet s, parent p):
			marquer s
			pour tout sommet v voisin de s
			|	si v n’est par marqué :
			|	|	si explorer_cycle(g, v, s) : renvoyer True
			|	sinon si v different de p : renvoyer True
			renvoyer False
	

Cet algo est quasiment identique à l’algo de recherche en profondeur. Les seules différences sont aux lignes 5 et 6.

Et voici son déroulement sur le graphe ci-dessous :

Dans un graphe orienté

Dans un graphe orienté, il faut tenir compte de l’orientation des arcs. Ainsi, un cycle de longueur 2 existe entre un sommet A et un sommet B dès lors qu’ils sont reliés par deux arcs de sens opposé. La condition voisin different de parent n’est plus adaptée.

		explorer_cycle_oriente(graphe g, sommet s):
			marquer s comme "en cours" (gris)
			pour tout sommet v voisin de s
			|   si v est marqué "en cours" (gris) :
			|   |   renvoyer True
			|   sinon si v n’est pas marqué "exploré" (noir) :
			|   |   si explorer_cycle_oriente(g, v) : renvoyer True
			marquer s comme "exploré" (noir)
			renvoyer False
	

On traitera un exemple en exercice.

Recherche de cycles

Graphe non orienté

Voici le code Python correspondant à l’algorithme de recherche d’un cycle dans un graphe non orienté. Ce code exécute de nombreux print pour pouvoir suivre son exécution.

			def explorer_cycle(graphe, u, parent, sommets_visites):
				print(f"\n––– explorer_cycle({u})")
				sommets_visites.add(u) # c’est la même variable que dans contient_cycle (référence)
				print(f"Les sommet visités à ce stade sont : {str(sommets_visites)}")
				print(f"Les voisins de {u} sont {str(graphe[u])}")
				# on examine les voisins du sommet en cours d’exploration
				for v in graphe[u]:
					print(f"voisin examiné : {v}")
					
					# si le voisin n’a pas encore été visité :
					if v not in sommets_visites:
						print(f"\t{v} n’est pas encore visité – je l’explore")
						if explorer_cycle(graphe, v, u, sommets_visites):
							print(f"\nIci explorer_cycle({u}) – explorer_cycle({v}) a renvoyé True 😀 – Je renvoie True aussi !")
							return True
						else:
							print(f"🖐️ explorer_cycle({v}) a renvoyé False – ce renvoi est ignoré par explorer_cycle({u})")
							print(f"\n––– retour vers explorer_cycle({u})")
					
					# si le voisin a été déjà visité et qu’il ne sagit pas du parent du sommet en cours d’exploration :
					elif v != parent:
						print(f"\t{v} a déjà été visité, mais il ne s’agit pas du prédécesseur de {u} – je renvoie True 😀")
						return True
					
					# si le voisin a été déjà visité mais qu’il s’agit du parent du sommet en cours d’exploration :
					else:
						print(f"\t{v} a déjà été visité, mais c’est le parent de {u} – je laisse béton.")
						
				# après examen de tous les voisins, s’ils sont tous visités si aucun cycle n’a été détecté
				print(f"L’examen des voisins de {u} est terminée - aucun cycle n’a été détecté 😣 – je renvoie False")
				return False

			def contient_cycle(graphe):
				sommets_visites = set()
				for sommet in graphe:
					if sommet not in sommets_visites:
						print(f"contient_cycle examine le sommet {sommet}")
						if explorer_cycle(graphe, sommet, None, sommets_visites): return True
				return False
		

1. Exécuter ce code sur le graphe donné en exemple dans le cours. Associer chaque print à son passage correspondant sur le slider.

2. Exécuter manuellement cet algorithme sur le graphique ci-dessous, puis utiliser le code Python donné et comparer vos étapes avec celles affichées sur par le code Python. Le sommet de départ sera le sommet (a) et les sommets dans les listes d’adjacence seront classés par ordre alphabétique.

3. Épurer ce code de toutes ses parties inutiles (y compris les commentaires).

Graphe orienté

1. En vous aidant des algorithmes formels de détection de cycle et de l’implémentation Python de sa version pour les graphes non orientés trouvée à la question précédente, proposer une implémentation Python de l’algorithme de détection des cycles dans des graphes orientés.

2. Tester vos algorithmes sur les graphes ci-dessous. Pour le graphe (2), tester avec et sans l’arc en rouge.