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

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

Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї часткового упорядкування і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав Корнейл (2004). Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів.

Приклад роботи алгоритму

Опис алгоритму

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

• Ініціалізувати послідовність множин вершин Σ що складається з однієї множини, яка містить усі вершини графу.
• Ініціалізувати порожню вихідну послідовність вершин.
• Поки Σ непорожня:
  • З першої множини в Σ взяти вершину v і видалити її з множини.
  • Якщо перша множина в Σ стала порожньою, видалити її з Σ.
  • Додати v в кінець вихідної послідовності вершин.
  • Для кожного ребра vw:
    • Визначити множину S в Σ яка містить w.
    • Якщо множина S ще не поділялася під час обробки v, створити нову порожню множину T і помістити її перед S у Σ.
    • Перемістити вершину w із S у T і, якщо S стала порожньою, видалити її з Σ.

Кожна вершина обробляється один раз, кожне ребро тестується тільки при обробці його двох вершин, і (в припущенні, що обробка операцій у послідовності множин Σ займає скінченний час) кожна ітерація внутрішнього циклу займає скінченний час. Отже, так само, як і для алгоритмів пошуку в глибину і пошуку в ширину, часова складність алгоритму є лінійною і становить $O(\vert V\vert +\vert E\vert )$.

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

Застосування

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

Література

• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Bretscher, Anna; Corneil, Derek; Habib, Michel; Paul, Christophe (2008), A simple linear time LexBFS cograph recognition algorithm, SIAM Journal on Discrete Mathematics, 22 (4): 1277—1296, doi:10.1137/060664690, архів оригіналу за 6 березня 2012, процитовано 23 червня 2021.
• 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, т. 3353, Springer-Verlag, с. 1—19, doi:10.1007/978-3-540-30559-0_1.
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing (PDF), Theoretical Computer Science, 234 (1–2): 59—84, doi:10.1016/S0304-3975(97)00241-7, архів оригіналу (PDF) за 26 липня 2011, процитовано 7 червня 2016 Архівна копія від 26 липня 2011 на Wayback Machine.
• Rose, D. J.; Tarjan, R. E.; Lueker, G. S. (1976), Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5 (2): 266—283, doi:10.1137/0205021.