Лексикографічний пошук у ширину
Лексикографічний пошук у ширину (англ. lexicographic breadth-first search LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішу[невідомий термін] послідовність вершин графу.
Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї часткового упорядкування і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав Корнейл (2004)[1]. Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів.
Опис алгоритму
Для роботи алгоритму слід задати вершину графу, з якої починається обхід. Опис алгоритму виглядає так:
- Ініціалізувати послідовність множин вершин Σ що складається з однієї множини, яка містить усі вершини графу.
- Ініціалізувати порожню вихідну послідовність вершин.
- Поки Σ непорожня:
- З першої множини в Σ взяти вершину v і видалити її з множини.
- Якщо перша множина в Σ стала порожньою, видалити її з Σ.
- Додати v в кінець вихідної послідовності вершин.
- Для кожного ребра vw:
- Визначити множину 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. 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..
- 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. Theoretical Computer Science 234 (1–2): 59–84. doi:10.1016/S0304-3975(97)00241-7. Архів оригіналу за 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..