Parcours de graphe

Contrairement au parcours d'arbres, le parcours de graphes peut nécessiter de visiter certains sommets plusieurs fois, car on ne sait pas forcément, avant d'accéder à un sommet, s'il a déjà été exploré. Plus les graphes sont denses , plus cette redondance est fréquente, ce qui augmente le temps de calcul ; inversement pour les graphes moins denses.

Il est donc généralement nécessaire de mémoriser les sommets déjà explorés par l'algorithme, afin de minimiser la fréquence de leurs visites (ou, dans le pire des cas, d'empêcher un parcours infini). Pour ce faire, on peut associer à chaque sommet du graphe un état de « couleur » ou de « visite » lors du parcours. Cet état est ensuite vérifié et mis à jour à chaque sommet visité. Si le sommet a déjà été visité, il est ignoré et le parcours s'arrête ; sinon, l'algorithme vérifie et met à jour l'état du sommet, puis poursuit son chemin.

Plusieurs cas particuliers de graphes impliquent la visite d'autres sommets au sein de leur structure et ne nécessitent donc pas l'enregistrement explicite de ces visites lors du parcours. Un exemple important est celui d'un arbre : lors d'un parcours, on peut supposer que tous les sommets « ancêtres » du sommet courant (et d'autres, selon l'algorithme) ont déjà été visités. Les parcours en profondeur et en largeur sont des adaptations d'algorithmes basés sur les arbres, qui se distinguent principalement par l'absence d'un sommet « racine » structurellement déterminé et par l'ajout d'une structure de données pour enregistrer l'état de visite lors du parcours.

Remarque : Si chaque sommet d’un graphe doit être parcouru par un algorithme arborescent (tel que DFS ou BFS), alors l’algorithme doit être appelé au moins une fois pour chaque composante connexe du graphe. Ceci est facilement réalisable en parcourant tous les sommets du graphe et en appliquant l’algorithme à chaque sommet non visité lors de son examen.

La procédure BFS( G , v ) crée une file Q, enfile v dans Q et marque v. Tant que Q n'est pas vide, on fait w ← Q.dequeue (). Si w est l'élément recherché, on le retourne. Pour chaque arête e de G.adjacentEdges ( w ) , on fait x ← G.adjacentVertex ( w , e ). Si x n'est pas marqué, on le marque , on l' enfile dans Q et on retourne null.

La recherche en largeur peut être utilisée pour résoudre de nombreux problèmes en théorie des graphes, par exemple :

• trouver tous les sommets à l'intérieur d'une composante connexe ;
• L'algorithme de Cheney ;
• trouver le chemin le plus court entre deux sommets ;
• tester la bipartition d'un graphe ;
• Numérotation des mailles de l'algorithme de Cuthill-McKee ;
• Algorithme de Ford-Fulkerson pour le calcul du débit maximal dans un réseau de flux ;
• sérialisation/désérialisation d'un arbre binaire vs sérialisation dans l'ordre trié (permet de reconstruire l'arbre de manière efficace) ;
• algorithmes de génération de labyrinthes ;
• algorithme de remplissage par inondation pour le marquage des régions contiguës d'une image bidimensionnelle ou d'un tableau n-dimensionnel ;
• analyse des réseaux et des relations.

Le problème de l'exploration de graphes peut être vu comme une variante du parcours de graphes. Il s'agit d'un problème en ligne , c'est-à-dire que les informations sur le graphe ne sont révélées que pendant l'exécution de l'algorithme. Un modèle courant est le suivant : étant donné un graphe connexe dont les arêtes ont des poids non négatifs, l'algorithme démarre à un sommet donné et connaît toutes les arêtes sortantes incidentes ainsi que les sommets situés à l'extrémité de ces arêtes, mais pas plus. Lorsqu'un nouveau sommet est visité, les arêtes sortantes incidentes et les sommets situés à l'extrémité de ces arêtes sont à nouveau connus. L'objectif est de visiter tous les n sommets et de revenir au sommet de départ, en minimisant la somme des poids des arêtes du parcours. Ce problème peut également être compris comme une version particulière du problème du voyageur de commerce , où le voyageur doit découvrir le graphe au fur et à mesure de son déplacement.

Pour les graphes généraux, l'algorithme le plus connu, valable pour les graphes non orientés et orientés, est un simple algorithme glouton :

• Dans le cas non orienté, le parcours glouton est au plus fois plus long qu'un parcours optimal. La meilleure borne inférieure connue pour tout algorithme déterministe en ligne est de 10/3.
  • Les graphes non orientés de poids unitaire peuvent être explorés avec un ratio compétitif de , qui est déjà une borne serrée sur les graphes Tadpole .
• Dans le cas d'un parcours orienté, le parcours glouton est au plus ( ) fois plus long qu'un parcours optimal. Ceci correspond à la borne inférieure de [ borne inférieure compétitive analogue de Ω ( n ) est également valable pour les algorithmes randomisés connaissant les coordonnées de chaque nœud dans un plongement géométrique. Si, au lieu de visiter tous les nœuds, il suffit de trouver un seul nœud « trésor », les bornes compétitives sont de l'ordre de Θ ( n² ) sur les graphes orientés ^de poids unitaire, aussi bien pour les algorithmes déterministes que pour les algorithmes randomisés.

Une séquence de parcours universelle est une suite d'instructions permettant de parcourir tout graphe régulier à un nombre donné de sommets, quel que soit le sommet de départ. Aleliunas et al. ont démontré, par une preuve probabiliste, l'existence d'une telle séquence, dont le nombre d'instructions est proportionnel à _pour tout graphe régulier à n sommets . Les étapes de la séquence sont relatives au nœud courant, et non absolues. Par exemple, si le nœud courant est _vⱼ et que _vⱼ possède d voisins , la séquence de parcours indiquera comme prochain nœud à visiter vⱼ⁺₁ le i ^-ème voisin de _{vⱼ ,} avec 1 ≤ i ≤ d .