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

StackOverflow https://stackoverflow.com/questions/413483

  •  03-07-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

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.

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

Это твое домашнее задание?

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

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

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

Это асимптотически оптимальный алгоритм, поскольку вы выполняете два DFSS (или BFSS), которые занимают 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)
      }
   }
}

Замените Queue стеком, и вы получите что-то вроде DFS.

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top