Лексикографический поиск в ширину

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную[неизвестный термин] последовательность вершин графа.

Алгоритм лексикографического поиска в ширину основан на идее разбиения на подмножества и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004)[1]. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраска полностью расщепляемых графов.

Файл:LBFS 2.gif

Описание алгоритма

Для работы алгоритма необходимо задать вершину графа, с которой начинается обход. Описание алгоритма выглядит следующим образом:

  • Инициализировать последовательность множеств вершин Σ состоящую из одного множества содержащего все вершины графа.
  • Инициализировать пустую выходную последовательность вершин.
  • Пока Σ непустое:
    • Из первого множества в Σ взять вершину v и удалить ее из множества.
    • Если первое множество в Σ стало пустым удалить его из Σ .
    • Добавить v в конец выходной последовательности вершин.
    • Для каждого ребра v-w:
      • Определить множество S в Σ которое содержит w.
      • Если множество S еще не разделялось при обработке v, создать новое пустое множество T и поместить его перед S в Σ.
      • Переместить вершину w из S в T и, если S стало пустым удалить его из Σ.

Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов поиска в глубину и поиска в ширину временная сложность алгоритма является линейной и составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math].

Алгоритм называется лексикографическим поиском в ширину потому, что получаемый порядок похож на результат алгоритма поиска в ширину, но дополнительно строки и столбцы матрицы смежности сортируются в лексикографическом порядке.

Применение

Алгоритм лексикографического поиска в ширину используется для распознавания хордальных графов, раскраски вполне сепарабельных графов. Для распознавания единичных интервальных и интервальных графов используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).

Примечания

Литература