Лексикографический поиск в ширину: различия между версиями
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Patarakin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Лексикографический поиск в ширину''' | '''Лексикографический поиск в ширину''' — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину|поиска в ширину]] и дает более упорядоченную последовательность вершин графа. | ||
Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004) | Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004) Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф| хордальных графов]], [[Раскраска графов| раскраска]] [[Дистанционно-наследуемый граф|полностью расщепляемых графов]]. | ||
https://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/LBFS_2.gif/330px-LBFS_2.gif | |||
== Описание алгоритма == | == Описание алгоритма == | ||
| Строка 27: | Строка 27: | ||
Для распознавания [[Интервальный граф|единичных интервальных и интервальных графов]] используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз). | Для распознавания [[Интервальный граф|единичных интервальных и интервальных графов]] используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз). | ||
---- | |||
[[Категория:Алгоритмы поиска]] | [[Категория:Алгоритмы поиска]] | ||
Текущая версия на 10:59, 20 октября 2022
Лексикографический поиск в ширину — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.
Алгоритм лексикографического поиска в ширину основан на идее разбиения на подмножества и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004) Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраска полностью расщепляемых графов.
Описание алгоритма
Для работы алгоритма необходимо задать вершину графа, с которой начинается обход. Описание алгоритма выглядит следующим образом:
- Инициализировать последовательность множеств вершин Σ состоящую из одного множества содержащего все вершины графа.
- Инициализировать пустую выходную последовательность вершин.
- Пока Σ непустое:
- Из первого множества в Σ взять вершину v и удалить ее из множества.
- Если первое множество в Σ стало пустым удалить его из Σ .
- Добавить v в конец выходной последовательности вершин.
- Для каждого ребра v-w:
- Определить множество S в Σ которое содержит w.
- Если множество S еще не разделялось при обработке v, создать новое пустое множество T и поместить его перед S в Σ.
- Переместить вершину w из S в T и, если S стало пустым удалить его из Σ.
Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов поиска в глубину и поиска в ширину временная сложность алгоритма является линейной и составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math].
Алгоритм называется лексикографическим поиском в ширину потому, что получаемый порядок похож на результат алгоритма поиска в ширину, но дополнительно строки и столбцы матрицы смежности сортируются в лексикографическом порядке.
Применение
Алгоритм лексикографического поиска в ширину используется для распознавания хордальных графов, раскраски вполне сепарабельных графов. Для распознавания единичных интервальных и интервальных графов используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).
