Имеется ориентированный граф (не обязательно связный), один или несколько узлов которого выделены как источники. Любой узел, доступный из любого из источников, считается «освещенным». Теперь предположим, что одно из ребер удалено. Проблема состоит в том, чтобы определить узлы, которые ранее горели и больше не горят.
Полагаю, аналогия с городской системой электроснабжения может быть рассмотрена.
Это проблема "достижимости динамического графа". Следующая статья должна быть полезной:
Полностью динамический алгоритм достижимости ориентированных графов с почти линейное время обновления. Лиам Родитти, Ури Цвик. Теория вычислений, 2002 г.
Это дает алгоритм с обновлениями времени O(m * sqrt(n)) (амортизированный) и запросами времени O(sqrt(n)) на возможно циклическом графе (где m — число ребер и n количество узлов). Если граф является ациклическим, его можно улучшить до обновлений за O(m) (амортизированных) и запросов за O(n/log n).
Всегда возможно, что вы могли бы сделать лучше, учитывая конкретную структуру вашей проблемы или обменяв пространство на время.
Если вместо просто «освещенных» или «неосвещенных» вы сохранили бы набор узлов, от которых узел запитывается или освещается, и рассматривали узел с пустым набором как «неосвещенный», а узел с непустым набором — как « горит», то удаление ребра будет означать просто удаление исходного узла из набора целевых узлов.
РЕДАКТИРОВАТЬ: Забыл это: и если вы удалите последний освещенный узел в наборе, пройдите по краям и удалите узел, который вы только что «не зажгли» из их набора (и, возможно, тоже пересечете его и т. д.)
РЕДАКТИРОВАТЬ2 (перефразировать для тафа): Во-первых: я неправильно понял исходный вопрос и подумал, что в нем говорилось, что для каждого узла уже известно, горит он или нет, что, как я перечитал сейчас, не упоминалось.
Однако, если для каждого узла в вашей сети вы храните набор, содержащий узлы, через которые он был освещен, вы можете легко пройти по графу от удаленного ребра и исправить любые освещенные/неосвещенные ссылки. Так, например, если у нас есть узлы A, B, C, D, как это: (хромая попытка ascii-арта)
A -> B >- D
\-> C >-/
Затем в узле A вы сохраните, что это был источник (и, следовательно, освещенный сам по себе), и в B, и в C вы сохраните, что они были освещены A, а в D вы сохраните, что он был освещен как A, так и C. .
Затем скажем, что мы удаляем ребро из B в D: В D мы удаляем B из списка освещенных источников, но он остается освещенным, поскольку он все еще освещается A. Далее, скажем, мы удаляем ребро из A в C после этого: A удаляется из набора C, и, таким образом, C больше не горит. Затем мы переходим по ребрам, исходящим из C, и удаляем C из набора D, который теперь также не освещен. В этом случае мы закончили, но если бы набор был больше, мы бы просто продолжили с D.
Этот алгоритм будет когда-либо посещать только те узлы, на которые непосредственно влияет удаление или добавление ребра, и поэтому (за исключением дополнительного хранилища, необходимого на каждом узле) он должен быть близок к оптимальному.
Это твоя домашняя работа?
Самое простое решение — сделать DFS (http://en.wikipedia.org/wiki/Depth-first_search) или BFS (http://en.wikipedia.org/wiki/Breadth-first_search) на исходном графе, начиная с исходных узлов. Это даст вам все оригинальные освещенные узлы.
Теперь удалите рассматриваемое ребро. Сделайте еще раз ДФС. Вы можете узлы, которые все еще остаются освещенными.
Выведите узлы, которые входят в первый набор, но не входят во второй.
Это асимптотически оптимальный алгоритм, поскольку вы выполняете две DFS (или BFS), которые занимают O (n + m) раз и пространство (где n = количество узлов, m = количество ребер), которые преобладают по сложности. Вам нужно как минимум o(n + m) времени и места, чтобы прочитать ввод, поэтому алгоритм оптимален.
Теперь, если вы хотите удалить несколько ребер, это было бы интересно. В этом случае мы будем говорить о динамических структурах данных. Это то, что вы намеревались?
РЕДАКТИРОВАТЬ: Принимая во внимание комментарии:
Псевдокод для BFS, который ищет все узлы, достижимые из любого из начальных узлов:
Queue q = [all starting nodes]
while (q not empty)
{
x = q.pop()
forall (y neighbour of x) {
if (y was not visited) {
visited[y] = true
q.push(y)
}
}
}
Замените очередь стеком, и вы получите что-то вроде DFS.
Насколько велики и насколько связаны графы? Вы можете сохранить все пути от исходных узлов ко всем другим узлам и искать узлы, все пути к этому узлу содержат одно из удаляемых ребер.
РЕДАКТИРОВАТЬ: немного расширить это описание
Выполните DFS с каждого исходного узла. Отслеживайте все пути, сгенерированные к каждому узлу (как ребра, а не вершины, поэтому нам нужно знать только задействованные ребра, а не их порядок, и поэтому мы можем использовать растровое изображение). Ведите подсчет для каждого узла количества путей от источника к узлу.
Теперь перебираем пути. Удалите все пути, содержащие удаленные ребра, и уменьшите значение счетчика для этого узла. Если счетчик узла уменьшился до нуля, он был освещен, а теперь нет.
Я бы сохранил информацию о подключенных исходных узлах на ребрах при построении графа (например, если ребро имеет подключение к источникам S1 и S2, его список источников содержит S1 и S2). И создайте узлы с информацией о входных ребрах и выходные края. Когда ребро удалено, обновите выходные ребра целевого узла этого ребра, учитывая входные ребра узла. И пройдите через все целевые узлы обновленных ребер, используя DFS или BFS. (В случае циклического графа рассмотрите возможность маркировки). При обновлении графа также можно найти узлы без какого-либо ребра, имеющего соединение с источником (освещенные->неосвещенные узлы). Однако это может быть не очень хорошим решением, если вы хотите удалить несколько ребер одновременно, поскольку это может привести к повторному обходу одних и тех же ребер.
