Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную[неизвестный термин] последовательность вершин графа.
Алгоритм лексикографического поиска в ширину основан на идее частичного упорядочивания[en] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004)[1]. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраска полностью расщепляемых графов[en].
Для работы алгоритма необходимо задать вершину графа, с которой начинается обход. Описание алгоритма выглядит следующим образом:
Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов поиска в глубину и поиска в ширину временная сложность алгоритма является линейной и составляет .
Алгоритм называется лексикографическим поиском в ширину потому, что получаемый порядок похож на результат алгоритма поиска в ширину, но дополнительно строки и столбцы матрицы смежности сортируются в лексикографическом порядке.
Алгоритм лексикографического поиска в ширину используется для распознавания хордальных графов, раскраски полностью расщепляемых графов[en]. Для распознавания единичных интервальных и интервальных графов используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .