Лексикографический поиск в ширину - Lexicographic breadth-first search

В компьютерной науке , лексикографический поиск в ширину или Lex-BFS является линейное время алгоритм для упорядочения вершин из в графике . Алгоритм отличается от поиска в ширину , но он производит упорядочение, совместимое с поиском в ширину.

Лексикографический алгоритм поиска в ширину основан на идее уточнения разбиения и был впервые разработан Дональдом Дж. Роузом, Робертом Э. Тарджаном и Джорджем С. Люкером ( 1976 ). Более подробный обзор этой темы представлен Corneil (2004) . Он был использован в качестве подпрограммы в других алгоритмах графа включая признание хордальных графов и оптимальную окраску от расстояния наследственных графов .

Задний план

Поиск в ширину алгоритм обычно определяется с помощью следующего процесса:

  • Инициализируйте очередь из вершин графа, используя начальную вершину графа как единственный элемент очереди.
  • Пока очередь не пуста, удалите (исключите из очереди ) вершину v из очереди и добавьте в очередь (поставьте в очередь) все другие вершины, которые могут быть достигнуты ребром из v, которые еще не были добавлены на предыдущих шагах.

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

  • Неоднократно выводите вершину v , выбирая на каждом шаге вершину v, которая еще не была выбрана и у которой есть предшественник (вершина, имеющая ребро на v ), как можно раньше в выводе.

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

  • Неоднократно выведите вершину v , выбирая на каждом шаге вершину v, которая еще не была выбрана и весь набор уже выведенных предшественников которой является как можно меньшим в лексикографическом порядке .

Итак, когда две вершины v и w имеют одного и того же самого раннего предшественника, более раннего, чем любые другие невыбранные вершины, стандартный алгоритм поиска в ширину упорядочит их произвольно. Вместо этого, в этом случае, алгоритм LexBFS будет выбирать между v и w в соответствии с порядком вывода их самых ранних предшественников. Если только один из них имеет второго самого раннего предшественника, который уже был выведен, выбирается этот. Если и v, и w имеют одного и того же самого раннего предшественника, тогда связь разрывается путем рассмотрения их предшественников, находящихся на третьем месте раньше, и так далее.

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

Алгоритм

Алгоритм лексикографического поиска в ширину заменяет очередь вершин стандартного поиска в ширину упорядоченной последовательностью наборов вершин. Множества в последовательности образуют разбиение остальных вершин. На каждом шаге вершина v из первого набора в последовательности удаляется из этого набора, и если это удаление приводит к тому, что набор становится пустым, то набор удаляется из последовательности. Затем каждый набор в последовательности заменяется двумя подмножествами: соседями v и несоседями v . Подмножество соседей размещается в последовательности раньше, чем подмножество несоседей. В псевдокоде алгоритм можно выразить следующим образом:

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

Каждая вершина обрабатывается один раз, каждое ребро проверяется только тогда, когда обрабатываются две его конечные точки, и (с соответствующим представлением для наборов в Σ, которое позволяет перемещать элементы из одного набора в другой за постоянное время) каждую итерацию внутреннего цикла занимает только постоянное время. Следовательно, как и более простые алгоритмы поиска в графах, такие как поиск в ширину и поиск в глубину , этот алгоритм требует линейного времени.

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

Приложения

Хордовые графы

Граф G определяется как хордовый, если его вершины имеют идеальный порядок исключения , такой порядок, что для любой вершины v соседи, которые появляются позже в этом порядке, образуют клику. В хордовом графе обратный лексикографическому порядку всегда является идеальным порядком исключения. Следовательно, можно проверить, является ли граф хордовым за линейное время, используя следующий алгоритм:

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

Это приложение послужило исходной мотивацией, которая побудила Роуза, Тарьяна и Люкера (1976) разработать алгоритм лексикографического поиска в ширину.

Раскраска графика

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

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

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

Другие приложения

Bretscher et al. (2008) описывают расширение лексикографического поиска в ширину, которое разрушает любые дополнительные связи, используя дополнительный граф входного графа. Как они показывают, это можно использовать для распознавания кографов в линейном времени. Habib et al. (2000) описывают дополнительные применения лексикографического поиска в ширину, включая распознавание графов сопоставимости и интервальных графов .

LexBFS заказ

Перечисление вершин графа называется упорядочением LexBFS, если оно является возможным результатом применения LexBFS к этому графу.

Позвольте быть граф с вершинами. Напомним, это набор соседей . Позвольте быть перечисление вершин . Перечисление является упорядочиванием LexBFS (с источником ), если для всех с существует такое, что .

Заметки

Рекомендации