Accueil🇫🇷Chercher

Parcours de graphe

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

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

Les algorithmes de parcours servent dans la résolution d'un certain nombre de problèmes parmi lesquels :

Complexité

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].

Notes et références

Articles liés

Sources

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.