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

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

Алгоритм лексикографического поиска в ширину основан на идее частичного упорядочивания и впервые был разработан Donald J. Rose, Robert E. Tarjan, and George S. Lueker^{[перевести]} (1976). Более детальный обзор темы был представлен Corneil (2004). Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраска полностью расщепляемых графов.

Описание алгоритма

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

• Инициализировать последовательность множеств вершин Σ состоящую из одного множества содержащего все вершины графа.
• Инициализировать пустую выходную последовательность вершин.
• Пока Σ непустое:
  • Из первого множества в Σ взять вершину v и удалить ее из множества.
  • Если первое множество в Σ стало пустым удалить его из Σ .
  • Добавить v в конец выходной последовательности вершин.
  • Для каждого ребра v-w:
    • Определить множество S в Σ которое содержит w.
    • Если множество S еще не разделялось при обработке v, создать новое пустое множество T и поместить его перед S в Σ.
    • Переместить вершину w из S в T и, если S стало пустым удалить его из Σ.

Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов поиска в глубину и поиска в ширину временная сложность алгоритма является линейной и составляет <math>O(\vert V \vert + \vert E \vert)</math>.

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

Применение

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

Литература

• 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), "[www.liafa.jussieu.fr/~habib/Documents/cograph.ps A simple linear time LexBFS cograph recognition algorithm]", SIAM Journal on Discrete Mathematics Т. 22 (4): 1277–1296, doi:[dx.doi.org/10.1137%2F060664690 10.1137/060664690], <www.liafa.jussieu.fr/~habib/Documents/cograph.ps> .
• Corneil, Derek G. (2004), [dx.doi.org/10.1007%2F978-3-540-30559-0_1 "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, vol. 3353, Lecture Notes in Computer Science, Springer-Verlag, сс. 1–19, DOI 10.1007/978-3-540-30559-0_1 .
• Habib, Michel; McConnell, Ross; Paul, Christophe & Viennot, Laurent (2000), "[www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf 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:[dx.doi.org/10.1016%2FS0304-3975%2897%2900241-7 10.1016/S0304-3975(97)00241-7], <www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf> .
• Rose, D. J.; Tarjan, R. E. & Lueker, G. S. (1976), "[dx.doi.org/10.1137%2F0205021 Algorithmic aspects of vertex elimination on graphs]", SIAM Journal on Computing Т. 5 (2): 266–283, DOI 10.1137/0205021 .

Отрывок, характеризующий Лексикографический поиск в ширину

– Да, он хотел зайти, – сказала Элен и внимательно посмотрела на Наташу.
Граф Илья Андреич опять сел на свое место.
– Ведь хороша? – шопотом сказал он Наташе.
– Чудо! – сказала Наташа, – вот влюбиться можно! В это время зазвучали последние аккорды увертюры и застучала палочка капельмейстера. В партере прошли на места запоздавшие мужчины и поднялась занавесь.
Как только поднялась занавесь, в ложах и партере всё замолкло, и все мужчины, старые и молодые, в мундирах и фраках, все женщины в драгоценных каменьях на голом теле, с жадным любопытством устремили всё внимание на сцену. Наташа тоже стала смотреть.


На сцене были ровные доски по средине, с боков стояли крашеные картины, изображавшие деревья, позади было протянуто полотно на досках. В середине сцены сидели девицы в красных корсажах и белых юбках. Одна, очень толстая, в шелковом белом платье, сидела особо на низкой скамеечке, к которой был приклеен сзади зеленый картон. Все они пели что то. Когда они кончили свою песню, девица в белом подошла к будочке суфлера, и к ней подошел мужчина в шелковых, в обтяжку, панталонах на толстых ногах, с пером и кинжалом и стал петь и разводить руками.
Мужчина в обтянутых панталонах пропел один, потом пропела она. Потом оба замолкли, заиграла музыка, и мужчина стал перебирать пальцами руку девицы в белом платье, очевидно выжидая опять такта, чтобы начать свою партию вместе с нею. Они пропели вдвоем, и все в театре стали хлопать и кричать, а мужчина и женщина на сцене, которые изображали влюбленных, стали, улыбаясь и разводя руками, кланяться.
После деревни и в том серьезном настроении, в котором находилась Наташа, всё это было дико и удивительно ей. Она не могла следить за ходом оперы, не могла даже слышать музыку: она видела только крашеные картоны и странно наряженных мужчин и женщин, при ярком свете странно двигавшихся, говоривших и певших; она знала, что всё это должно было представлять, но всё это было так вычурно фальшиво и ненатурально, что ей становилось то совестно за актеров, то смешно на них. Она оглядывалась вокруг себя, на лица зрителей, отыскивая в них то же чувство насмешки и недоумения, которое было в ней; но все лица были внимательны к тому, что происходило на сцене и выражали притворное, как казалось Наташе, восхищение. «Должно быть это так надобно!» думала Наташа. Она попеременно оглядывалась то на эти ряды припомаженных голов в партере, то на оголенных женщин в ложах, в особенности на свою соседку Элен, которая, совершенно раздетая, с тихой и спокойной улыбкой, не спуская глаз, смотрела на сцену, ощущая яркий свет, разлитый по всей зале и теплый, толпою согретый воздух. Наташа мало по малу начинала приходить в давно не испытанное ею состояние опьянения. Она не помнила, что она и где она и что перед ней делается. Она смотрела и думала, и самые странные мысли неожиданно, без связи, мелькали в ее голове. То ей приходила мысль вскочить на рампу и пропеть ту арию, которую пела актриса, то ей хотелось зацепить веером недалеко от нее сидевшего старичка, то перегнуться к Элен и защекотать ее.
В одну из минут, когда на сцене всё затихло, ожидая начала арии, скрипнула входная дверь партера, на той стороне где была ложа Ростовых, и зазвучали шаги запоздавшего мужчины. «Вот он Курагин!» прошептал Шиншин. Графиня Безухова улыбаясь обернулась к входящему. Наташа посмотрела по направлению глаз графини Безуховой и увидала необыкновенно красивого адъютанта, с самоуверенным и вместе учтивым видом подходящего к их ложе. Это был Анатоль Курагин, которого она давно видела и заметила на петербургском бале. Он был теперь в адъютантском мундире с одной эполетой и эксельбантом. Он шел сдержанной, молодецкой походкой, которая была бы смешна, ежели бы он не был так хорош собой и ежели бы на прекрасном лице не было бы такого выражения добродушного довольства и веселия. Несмотря на то, что действие шло, он, не торопясь, слегка побрякивая шпорами и саблей, плавно и высоко неся свою надушенную красивую голову, шел по ковру коридора. Взглянув на Наташу, он подошел к сестре, положил руку в облитой перчатке на край ее ложи, тряхнул ей головой и наклонясь спросил что то, указывая на Наташу.