Dans ce travail on a fait une vaste présentation sur les algorithmes d'explorations des graphes mais plus précisément le parcours en largeurs lexicographic (LexBFS).
Ainsi on a défini des algorithmes basées sur LexBFS pour la reconnaissance de graphe (triangulé, intervalle) et leurs importances dans la résolution de certains problèmes de tous les jours (ex : Problème de l'emploi du temps).