4824
правки
Полностью динамический алгоритм достижимости с единственным источником: различия между версиями
Материал из WEGA
Полностью динамический алгоритм достижимости с единственным источником (посмотреть исходный код)
Версия от 03:37, 20 февраля 2018
, 20 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
'''Определение 1 (Полностью динамическая задача достижимости'''). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 1 (Полностью динамическая задача достижимости'''). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
• ''insert(u,v)'': вставка дуги (u, v) в граф; | • ''insert(u, v)'': вставка дуги (u, v) в граф; | ||
• ''delete(u,v)'': удаление дуги (u, v) из графа; | • ''delete(u, v)'': удаление дуги (u, v) из графа; | ||
• ''reachable(x,y)'': возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае. | • ''reachable(x, y)'': возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае. | ||
Далее будет исследована версия полностью динамической задачи достижимости для случая с единственным источником, в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом. | Далее будет исследована версия полностью динамической задачи достижимости для случая ''с единственным источником'', в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом. | ||
'''Определение 2 (Полностью динамическая задача достижимости с единственным источником)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | |||
• ''insert(u,v)'': вставка дуги (u, v) в граф; | • ''insert(u, v)'': вставка дуги (u, v) в граф; | ||
• ''delete(u,v)'': удаление дуги (u, v) из графа; | • ''delete(u, v)'': удаление дуги (u, v) из графа; | ||
• ''reachable(y)'': возвращает true, если существует ориентированный путь между вершиной-источником s и вершиной y, и false в противном случае. | • ''reachable(y)'': возвращает ''true'', если существует ориентированный путь между вершиной-источником s и вершиной y, и ''false'' в противном случае. | ||
''' | '''Подходы к решению''' | ||
Простое решение этой задачи заключается в хранении явной информации о достижимости любой вершины из источника и обновлении этой информации при помощи любого алгоритма обхода графа из вершины s после каждой операции вставки или удаления. Такой подход требует O(m + n) времени на операцию, а последующие запросы о достижимости могут быть выполнены за константное время. | |||
Еще одним простым решением является ответ на запросы путем поточечного вычисления достижимости, без необходимости | |||
Еще одним простым решением является ответ на запросы путем поточечного вычисления достижимости, без необходимости сохранения явной информации о достижимости после каждой вставки или удаления. Это можно выполнить за время O(m + n) при помощи любого алгоритма обхода графа. Подобный подход позволяет давать ответы на запросы за время O(m + n) и выполнять обновления за константное время. Заметим, что при использовании обоих подходов время выполнения самой медленной операции составляет O(m + n), что для плотных графов доходит до <math>O(n^2) \;</math>. | |||
