Существует ли правильный алгоритм для решения проблемы удаления ребер?

Question

Существует ориентированный граф (необязательно связанный), один или несколько узлов которого различаются как источники. Любой узел, доступный из любого из источников, считается «освещенным». Теперь предположим, что один из ребер удален. Проблема состоит в том, чтобы определить узлы, которые были ранее освещены и больше не светятся.

Можно предположить аналогию, подобную городской системе электроснабжения.

Answer 1

Это проблема "динамической доступности графа". Следующая статья должна быть полезной:

Полностью динамический алгоритм достижимости для ориентированных графов с почти линейным временем обновления. Лиам Родитти, Ури Цвик. Теория вычислений , 2002.

Это дает алгоритм с O (m * sqrt (n)) - обновлениями времени ( амортизируется ) и O (sqrt (n)) - запросами времени на возможно циклическом графе (где m количество ребер и п число узлов). Если график является ациклическим, его можно улучшить до запросов времени обновления O (m) ( амортизируется ) и запросов времени O (n / log n).

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

Answer 2

Если вместо того, чтобы просто «горит» или «не горит», вы бы сохранили набор узлов, от которых включается или горит узел, и рассматривали бы узел с пустым набором как «не горит», а узел с непустым Если установлено «горит», то удаление ребра будет просто включать удаление исходного узла из набора целевого узла.

РЕДАКТИРОВАТЬ: Забыли это: А если вы удалите последний подсвеченный узел в наборе, пройдитесь по краям и удалите только что «неосвещенный» узел из их набора (и, возможно, пройдитесь оттуда тоже и т. Д.)

EDIT2 (перефразировать для тафа): Во-первых: я неправильно прочитал исходный вопрос и подумал, что в нем говорится, что для каждого узла уже было известно, что он светится или не светится, что, как я сейчас перечитывал, не упоминалось.

Однако, если для каждого узла в вашей сети вы сохраняете набор, содержащий узлы, через которые он прошел, вы можете легко пройти по графику от удаленного края и исправить любые подсвеченные / неосвещенные ссылки. Так, например, если у нас есть узлы A, B, C, D, например: (неудачная попытка в ascii art)

A -> B >- D
 \-> C >-/

Тогда в узле A вы должны хранить, что это был источник (и, следовательно, освещен сам по себе), и в B и C вы должны хранить, что они были освещены A, а в D вы должны хранить, что он был освещен обоими А и С.

Затем скажите, что мы удаляем ребро из B в D: В D мы удаляем B из списка освещенных источников, но он остается освещенным, поскольку он все еще освещается A. Затем, скажем, мы удаляем ребро из A в C после что: A удаляется из набора C, и, следовательно, C больше не горит. Затем мы пересекаем ребра, которые возникли в C, и удаляем C из множества D, которое теперь тоже не горит. В этом случае мы закончили, но если бы набор был больше, мы бы просто продолжили с D.

Этот алгоритм будет когда-либо посещать только те узлы, на которые непосредственно влияет удаление или добавление ребра, и поэтому (кроме дополнительной памяти, необходимой для каждого узла) должен быть близок к оптимальному.

Answer 3

Это ваша домашняя работа?

Самое простое решение - сделать DFS (http://en.wikipedia.org/wiki/Depth-first_search) или BFS (http://en.wikipedia.org/wiki/Breadth-first_search)) на исходном графике, начиная с исходных узлов. Это даст вам все исходные освещенные узлы.

Теперь удалите рассматриваемый край. Сделай снова DFS. Вы можете узлы, которые все еще остаются освещенными.

Вывести узлы, которые появляются в первом наборе, но не во втором.

Это асимптотически оптимальный алгоритм, так как вы выполняете две DFS (или BFS), которые занимают O (n + m) времени и пространства (где n = количество узлов, m = количество ребер), которые доминируют в сложности. Вам нужно как минимум o (n + m) время и пространство для чтения ввода, поэтому алгоритм оптимален.

Теперь, если вы хотите удалить несколько ребер, это было бы интересно. В этом случае мы будем говорить о динамических структурах данных. Это то, что вы намеревались?

РЕДАКТИРОВАТЬ: с учетом комментариев:

• не подключен не является проблемой, так как узлы в недоступных подключенных компонентах не будут доступны во время поиска
• есть умный способ сделать DFS или BFS со всех узлов одновременно (я опишу BFS). Вы просто должны поместить их все в начало в стек / очередь.

Псевдокод для 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.

Answer 4

Я буду хранить информацию о подключенных исходных узлах по краям при построении графа (например, если у ребра есть связь с источниками S1 и S2, его список источников содержит S1 и S2) И создавать узлы с информацией входные ребра и выходные ребра. Когда ребро удалено, обновите выходные ребра целевого узла этого ребра, учитывая входные ребра узла. И пройти через все целевые узлы обновленных ребер, используя DFS или BFS. (В случае графа цикла рассмотрите маркировку). При обновлении графика также можно найти узлы без какого-либо ребра, имеющего исходное соединение (светящиеся-> неосвещенные узлы). Тем не менее, это может быть не лучшим решением, если вы хотите удалить несколько ребер одновременно, поскольку это может привести к пересечению одних и тех же ребер снова и снова.

Answer 5

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

РЕДАКТИРОВАТЬ: немного расширить это описание

Сделать DFS от каждого исходного узла. Отслеживайте все пути, сгенерированные для каждого узла (как ребра, а не вершины, поэтому нам нужно знать только задействованные ребра, а не их порядок, поэтому мы можем использовать растровое изображение). Ведите подсчет для каждого узла количества путей от источника к узлу.

Теперь перебираем пути. Удалите все пути, содержащие удаленные ребра, и уменьшите счетчик для этого узла. Если счетчик узлов уменьшен до нуля, он горит, а теперь нет.