Лексикографічний пошук у ширину ( LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішу послідовність вершин графу.
Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав (2004). Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів.
Опис алгоритму Для роботи алгоритму слід задати вершину графу, з якої починається обхід. Опис алгоритму виглядає так:
Ініціалізувати послідовність множин вершин Σ що складається з однієї множини, яка містить усі вершини графу. Ініціалізувати порожню вихідну послідовність вершин. Поки Σ непорожня: З першої множини в Σ взяти вершину v і видалити її з множини. Якщо перша множина в Σ стала порожньою, видалити її з Σ. Додати v в кінець вихідної послідовності вершин. Для кожного ребра vw: Визначити множину S в Σ яка містить w. Якщо множина S ще не поділялася під час обробки v, створити нову порожню множину T і помістити її перед S у Σ. Перемістити вершину w із S у T і, якщо S стала порожньою, видалити її з Σ.
Кожна вершина обробляється один раз, кожне ребро тестується тільки при обробці його двох вершин, і (в припущенні, що обробка операцій у послідовності множин Σ займає скінченний час) кожна ітерація внутрішнього циклу займає скінченний час. Отже, так само, як і для алгоритмів пошуку в глибину і пошуку в ширину, часова складність алгоритму є лінійною і становить .
Алгоритм називається лексикографічним пошуком у ширину тому, що отримуваний порядок схожий на результат алгоритму пошуку в ширину, але додатково рядки і стовпці матриці суміжності упорядковуються в лексикографічному порядку.
Застосування Алгоритм лексикографічного пошуку в ширину використовується для розпізнавання хордальних графів, розфарбовування цілком сепарабельних графів. Для розпізнавання графів порівнянності та інтервальних графів використовують багатомахові алгоритми (алгоритм лексикографічного пошуку в ширину з варіаціями застосовується кілька разів).
Примітки
Література . . . Архівна копія від 26 липня 2011 на Wayback Machine. .