Parcours de graphe
Cet article est une ébauche concernant les mathématiques et l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial. Un cas particulier important est le parcours d'arbre.
Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit).
Algorithmes de parcours modifier
Il existe de nombreux algorithmes de parcours. Les plus couramment décrits sont le parcours en profondeur et le parcours en largeur. L'algorithme de Dijkstra et l'algorithme de Prim font également partie de cette catégorie.
Les algorithmes de parcours n'ont pas une finalité intrinsèque. Ils servent comme outil pour étudier une propriété globale du graphe, comme la connexité ou la forte connexité ou l'existence d'un point d'articulation[1].
Un parcours d'un graphe est un procédé qui permet de choisir, à partir des sommets visités, le sommet suivant à visiter. Le problème consiste à déterminer un ordre sur les visites des sommets. Une fois le choix fait, l’ordre des visites induit une numérotation des sommets visités (l'ordre de leur découverte) et un choix sur l'arc ou l’arête utilisé pour atteindre un nouveau sommet à partir des sommets déjà visités.
Les arcs ou arêtes distingués forment une arborescence ou un arbre, et les numéros des sommets sont croissants sur les chemins de l’arborescence ou les chaînes de l'arbre depuis la racine.
Algorithmes utilisant des parcours de graphes modifier
Les algorithmes de parcours servent dans la résolution d'un certain nombre de problèmes parmi lesquels :
- connexité et forte connexité ;
- existence d'un circuit ou d'un cycle (ce qu'on appelle tri topologique) ;
- calcul des plus courts chemins (notamment l'algorithme de Dijkstra) ;
- calcul d'un arbre recouvrant (notamment l'algorithme de Prim) ;
- algorithmes pour les flots maximaux (comme l'algorithme de Ford-Fulkerson).
Complexité modifier
Pour la réalisation d'un parcours, il est en général nécessaire de mémoriser quels sont les sommets déjà explorés par l'algorithme, de sorte de ne pas répéter une visite d'un sommet déjà exploré. De manière pratique, cela peut être réalisé par une marque distinctive (une « couleur » ou un état spécial) associé à chaque sommet et qui est maintenu attesté durant l’exécution de l'algorithme. Lors de l’exploration d'un sommet, on le marque comme nouvellement découvert à la première visite, et on arrête la visite lors d'une rencontre ultérieure. L'espace occupé par de tels indicateurs est constant pour chaque sommet. Une telle mémorisation n’est pas nécessaire pour les parcours d'arbres.
La complexité d'un algorithme de parcours en lui-même est en , où est le nombre de sommets et le nombre d'arcs ou d'arêtes; il est donc linéaire[1]. Un algorithme utilisant comme brique de base un algorithme de parcours peut être de complexité supérieure. L’algorithme de test de planarité de Robert Tarjan exploite des numérotations induites par plusieurs parcours[2].
Description des algorithmes modifier
Parcours en largeur modifier
Caractéristiques modifier
- Les sommets sont visités dans un ordre croissant de leur distance au sommet source.
- La visite commence par le sommet source et se propage ensuite vers les sommets voisins les plus proches.
- Les sommets les plus éloignés du sommet source sont visités en dernier.
Fonctionnement modifier
L'algorithme fonctionne en construisant une file de priorité contenant tous les sommets du graphe qui n'ont pas encore été visités. Le sommet le plus proche du sommet source est placé en haut de la file de priorité. Ensuite, l'algorithme extrait le sommet le plus proche de la file de priorité et le visite. Pour chaque voisin non visité de ce sommet, l'algorithme ajoute le voisin à la file de priorité.
L'algorithme continue d'extraire des sommets de la file de priorité et de les visiter jusqu'à ce que la file de priorité soit vide.
Implémentation modifier
def breadth_first_search(graph, source):
"""
Explore un graphe en largeur, en commençant par le sommet source.
Args:
graph: Le graphe.
source: Le sommet source.
Returns:
Une liste des sommets du graphe, dans l'ordre dans lequel ils ont été visités.
"""
# Initialisation
visited = set()
queue = [source]
# Boucle principale
while queue:
u = queue.pop(0)
visited.add(u)
# On explore les voisins de u
for v in graph[u]:
if v not in visited:
queue.append(v)
return visited
Applications modifier
Trouver le plus court chemin entre deux sommets.
Parcours en profondeur modifier
Caractéristiques modifier
- Les sommets sont visités dans un ordre croissant de leur profondeur.
- La visite commence par le sommet source et se propage ensuite vers les sommets les plus profonds.
- Les sommets les plus proches du sommet source sont visités en dernier.
Fonctionnement modifier
L'algorithme fonctionne en construisant une pile contenant tous les sommets du graphe qui n'ont pas encore été visités. Le sommet le plus profond du pile est placé en haut de la pile. Ensuite, l'algorithme extrait le sommet le plus profond de la pile et le visite. Pour chaque voisin non visité du sommet actuel, l'algorithme ajoute le voisin à la pile.
L'algorithme continue d'extraire des sommets de la pile et de les visiter jusqu'à ce que la pile soit vide.
Implémentation modifier
def depth_first_search(graph, source):
"""
Explore un graphe en profondeur, en commençant par le sommet source.
Args:
graph: Le graphe.
source: Le sommet source.
Returns:
Une liste des sommets du graphe, dans l'ordre dans lequel ils ont été visités.
"""
# Initialisation
visited = set()
stack = [source]
# Boucle principale
while stack:
u = stack.pop()
visited.add(u)
# On explore les voisins de u
for v in graph[u]:
if v not in visited:
stack.append(v)
return visited
Applications modifier
Trouver les composantes fortement connexe d'un graphe.
Notes et références modifier
Articles liés modifier
- Algorithme de parcours en profondeur
- Algorithme de parcours en largeur
- Algorithme de Dijkstra des plus courts chemins
- Algorithme de Kosaraju de test de forte connexité
- Algorithme de Tarjan de test de forte connexité
- Arbre de Trémaux
Sources modifier
- Sylvie Borne, « Exploration d'un graphe », Cours : Algorithmique de graphes, chapitre 3, Ingénieurs sup Galilée, 2012-2013 (consulté le ).
- Robert Cori, « L’algorithme de test de planarité de R. E. Tarjan », Bulletin de la société informatique de France, no 4, , p. 55-65 (lire en ligne).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition]
