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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї часткового упорядкування[en] і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав Корнейл[en] (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, архів оригіналу за 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[en], 5 (2): 266—283, doi:10.1137/0205021.