Перегляд вихідного коду сторінки Лексикографічний пошук у ширину

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

Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї {{Не перекладено|Часткове упорядкування|часткового упорядкування|en|Partition refinement}} і вперше його розробили Роуз, [[Роберт Андре Тарджан|Тарджан]] і Люкер (1976). Детальніший огляд теми надав {{Нп|Дерек Корнейл|Корнейл|en|Derek Corneil}} (2004){{Sfnp|Corneil|2004}}. Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання [[Хордальний граф|хордальних графів]], [[Розфарбовування графів|розфарбовування]] [[Дистанційно-успадковуваний граф|повністю розщеплюваних графів]].
[[Файл:LBFS_2.gif|міні|Приклад роботи алгоритму]]

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

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

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

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

== Застосування ==
Алгоритм лексикографічного пошуку в ширину використовується для розпізнавання [[Хордальний граф|хордальних графів]], [[Розфарбовування графів|розфарбовування]] [[Дистанційно-успадковуваний граф|цілком сепарабельних графів]]. Для розпізнавання [[Граф порівнянності|графів порівнянності]] та [[Інтервальний граф|інтервальних графів]] використовують багатомахові алгоритми (алгоритм лексикографічного пошуку в ширину з варіаціями застосовується кілька разів).

== Примітки ==
{{Reflist}}

== Література ==
* {{Citation|last1=Brandstädt|first1=Andreas|author1-link=Андреас Брандштедт|last2=Le|first2=Van Bang|last3=Spinrad|first3=Jeremy|title=Graph Classes: A Survey|publisher=SIAM Monographs on Discrete Mathematics and Applications|year=1999|isbn=0-89871-432-X}}.
* {{Citation|first1=Anna|title=A simple linear time LexBFS cograph recognition algorithm|doi=10.1137/060664690|pages=1277–1296|year=2008|issue=4|volume=22|journal=[[SIAM Journal on Discrete Mathematics]]|last4=Paul|last1=Bretscher|first4=Christophe|last3=Habib|first3=Michel|author2-link=Дерек Корнейл|last2=Corneil|first2=Derek|url=http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps|accessdate=23 червня 2021|archive-date=6 березня 2012|archive-url=https://web.archive.org/web/20120306002958/http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps}}.
* {{Citation|first=Derek G.|last=Corneil|author-link=Дерек Корнейл|contribution=Lexicographic breadth first search – a survey|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3353|year=2004|pages=1–19|doi=10.1007/978-3-540-30559-0_1|ref=harv}}.
* {{Citation|first1=Michel|volume=234|archivedate=2011-07-26|archiveurl=https://web.archive.org/web/20110726091134/http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf|doi=10.1016/S0304-3975(97)00241-7|issue=1–2|url=http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf|pages=59–84|year=2000|journal=Theoretical Computer Science|last1=Habib|title=Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing|last4=Viennot|first4=Laurent|last3=Paul|first3=Christophe|last2=McConnell|first2=Ross|access-date=2016-06-07}} Архівна копія від 26 липня 2011 на Wayback Machine.
* {{Citation|first1=D. J.|last1=Rose|first2=R. E.|last2=Tarjan|author2-link=Роберт Андре Тарджан|first3=G. S.|last3=Lueker|year=1976|title=Algorithmic aspects of vertex elimination on graphs|journal={{нп|SIAM Journal on Computing}}|volume=5|pages=266–283|issue=2|doi=10.1137/0205021}}.

[[Категорія:Алгоритми пошуку]]
[[Категорія:Алгоритми на графах]]