Лексикографічний пошук у ширину англ lexicographic breadth first search LBFS або Lex BFS алгоритм упорядкування вершин г

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

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

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

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

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

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

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

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

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

Примітки

Corneil, (2004).

Література

; 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.

[FOOTNOTECorneil2004-1] Corneil, (2004).