Лексикографический поиск в ширину (англ.lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную[неизвестный термин] последовательность вершин графа.
Алгоритм лексикографического поиска в ширину основан на идее разбиения на подмножества и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004)[1]. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраскаполностью расщепляемых графов.
Из первого множества в Σ взять вершину v и удалить ее из множества.
Если первое множество в Σ стало пустым удалить его из Σ .
Добавить v в конец выходной последовательности вершин.
Для каждого ребра v-w:
Определить множество S в Σ которое содержит w.
Если множество S еще не разделялось при обработке v, создать новое пустое множество T и поместить его перед S в Σ.
Переместить вершину w из S в T и, если S стало пустым удалить его из Σ.
Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов поиска в глубину и поиска в ширинувременная сложность алгоритма является линейной и составляет .
Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN0-89871-432-X.
Corneil, Derek G. (2004), "Lexicographic breadth first search – a survey", Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, pp. 1—19, doi:10.1007/978-3-540-30559-0_1.
