LexBFS

LexBFS, ou parcours en largeur lexicographique est un algorithme de théorie des graphes. C'est un raffinement de l'algorithme de parcours en largeur (BFS pour Breadth First Search en anglais). Ce parcours est très utile pour étudier certaines classes de graphes et pour obtenir des algorithmes de reconnaissance rapides de ces classes. L'algorithme de parcours en largeur (Breadth First Search algorithm ou BFS) est usuellement défini de la manière suivante: Initialiser une de sommets du graphe avec le nœud de départ du parcours comme unique élément de la file. Tant que la file est non-vide, retirer (défiler) le sommet v, marquer v et ajouter à la file (enfiler) tous les sommets voisins de v qui n'ont pas été marqués dans une étape antérieure. Cependant, plutôt que de définir le sommet à choisir à chaque itération d'une manière impérative (comme on le fait par l'opération défiler), la même suite de sommets peut être définie de manière déclarative par les propriétés de ces sommets. Autrement dit, un parcours en largeur standard est produit par la répétition de la règle suivante: Choisir à chaque étape le sommet v qui n'a pas déjà été choisi et dont un prédécesseur a été choisi le plus tôt possible au cours du processus. Dans certains cas, cet ordonnancement des sommets par l'ordre de choix de leurs prédécesseurs peut mener à des égalités (plusieurs sommets peuvent avoir le même premier prédécesseur). Dans ce cas, l'ordre dans lequel on choisit ces sommets peut être arbitraire. L'ordre de choix du LexBFS diffère d'un parcours en largeur standard en résolvant ces égalités par une règle systématique. En effet, dans le parcours en largeur lexicographique, l'ordre de choix est produit par la règle suivante: Choisir à chaque étape le sommet v qui n'a pas déjà été choisi et dont l'ensemble des prédécesseurs déjà choisis est aussi petit que possible en considérant l'ordre lexicographique. Autrement dit, si deux sommets v et w ont le même premier prédécesseur (choisi avant tout prédécesseur de tout autre sommet encore non-choisi), LexBFS choisit entre v et w en fonction de l'ordre de leur second prédécesseur.