Лексикографічний пошук у ширину (англ. lexicographic breadth-first search LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішу[] послідовність вершин графу.
Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї [en] і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав [en] (2004). Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMlk1TDB4Q1JsTmZNaTVuYVdZdk1qSXdjSGd0VEVKR1UxOHlMbWRwWmc9PS5naWY=.gif)
Опис алгоритму
Для роботи алгоритму слід задати вершину графу, з якої починається обхід. Опис алгоритму виглядає так:
- Ініціалізувати послідовність множин вершин Σ що складається з однієї множини, яка містить усі вершини графу.
- Ініціалізувати порожню вихідну послідовність вершин.
- Поки Σ непорожня:
- З першої множини в Σ взяти вершину v і видалити її з множини.
- Якщо перша множина в Σ стала порожньою, видалити її з Σ.
- Додати v в кінець вихідної послідовності вершин.
- Для кожного ребра vw:
- Визначити множину S в Σ яка містить w.
- Якщо множина S ще не поділялася під час обробки v, створити нову порожню множину T і помістити її перед S у Σ.
- Перемістити вершину w із S у T і, якщо S стала порожньою, видалити її з Σ.
Кожна вершина обробляється один раз, кожне ребро тестується тільки при обробці його двох вершин, і (в припущенні, що обробка операцій у послідовності множин Σ займає скінченний час) кожна ітерація внутрішнього циклу займає скінченний час. Отже, так само, як і для алгоритмів пошуку в глибину і пошуку в ширину, часова складність алгоритму є лінійною і становить .
Алгоритм називається лексикографічним пошуком у ширину тому, що отримуваний порядок схожий на результат алгоритму пошуку в ширину, але додатково рядки і стовпці матриці суміжності упорядковуються в лексикографічному порядку.
Застосування
Алгоритм лексикографічного пошуку в ширину використовується для розпізнавання хордальних графів, розфарбовування цілком сепарабельних графів. Для розпізнавання графів порівнянності та інтервальних графів використовують багатомахові алгоритми (алгоритм лексикографічного пошуку в ширину з варіаціями застосовується кілька разів).
Примітки
Література
- ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN .
- Bretscher, Anna; ; Habib, Michel; Paul, Christophe (2008), , SIAM Journal on Discrete Mathematics, 22 (4): 1277—1296, doi:10.1137/060664690, архів оригіналу за 6 березня 2012, процитовано 23 червня 2021.
- (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), (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, [en], 5 (2): 266—283, doi:10.1137/0205021.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет