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.

Contexte

L'algorithme de parcours en largeur (Breadth First Search algorithm ou BFS) est usuellement défini de la manière suivante:

• Initialiser une file 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. Si v et w ont le même second prédécesseur, alors l'égalité est résolue en considérant leur troisième prédécesseur et ainsi de suite.

Utiliser directement cette règle d'ordonnancement mènerait à un algorithme inefficace, c'est pourquoi le parcours en largeur lexicographique utilise une structure de données adaptée pour produire l'ordonnancement efficacement, de la même manière qu'un parcours en largeur standard utilise une structure de données de file pour produire un ordre efficacement.

Description

Description simplifiée

Le principe est grossièrement de faire un parcours en largeur en privilégiant les nœuds qui sont les moins « récemment vus ».

Un pseudo code est le suivant, pour un graphe de n nœuds[1] :

• Initialement chaque nœud a une étiquette vide, et n'a pas de numéro.
• pour i allant de n à 1 :
  • Choisir un sommet v n'ayant pas de numéro, et ayant la plus grande étiquette en ordre lexicographique.
  • Associer le numéro i à v.
  • Pour tout sommet adjacent à v n'ayant pas de numéro, concaténer i à l'étiquette.

Description détaillée

Le parcours en largeur lexicographique remplace la file d'un parcours en largeur standard par une suite ordonnée d'ensembles de sommets. Les ensembles de la suite réalisent une partition de l'ensemble des sommets non-encore choisis. À chaque étape, un sommet v du premier ensemble de la suite est retiré de cet ensemble, et si cet ensemble est maintenant vide, il est retiré de la suite. Ensuite, tout ensemble de la suite est partitionné en deux sous-ensembles: les voisins de v et les autres sommets, non-voisins de v. Le sous-ensemble des voisins est placé avant le sous-ensemble des non-voisins dans la liste.

En pseudo-code, l'algorithme peut être exprimé de la manière suivante:

• Initialiser la séquence Σ d'ensembles à un unique ensemble contenant tous les sommets.
• Tant que Σ non-vide:
  • trouver un sommet v dans le premier ensemble de Σ,
  • si le premier ensemble de Σ est vide, le retirer de Σ,
  • ajouter v à la sortie,
  • pour chaque voisin w de v tel que w appartient à un ensemble S de Σ,
    • si l'ensemble S contenant w n'a pas été modifié pendant le traitement de v, créer un ensemble T vide et le placer devant S dans la suite Σ,
    • sinon, T désigne l'ensemble créé devant S dans la suite Σ pendant le traitement de v,
    • déplacer w de S à T, si S est vide, le retirer de la suite.

Chaque sommet est traité une seule fois, chaque lien est traité lorsque ses deux extrémités ont été traitées. Avec une représentation adaptée de la suite d'ensembles Σ, qui permet de déplacer les éléments d'un ensemble à un autre en temps constant, chaque itération de la boucle intérieure est réalisée en temps constant. Donc cet algorithme peut être réalisé en temps linéaire.

Applications

LexBFS permet notamment de reconnaître les graphes cordaux en temps linéaire[1].

Voir aussi

• Raffinement de partition

Notes et références

1. D. J. Rose, R. E. Tarjan et G. S. Lueker, « Algorithmic aspects of vertex elimination on graphs », SIAM Journal on Computing, vol. 5, n^o 2,‎ 1976, p. 266-283 (DOI 10.1137/0205021).