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

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

Простое решение состоит в том, чтобы сделать 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)
      }
   }
}

Очередь замены со Стеком и Вы получаете своего рода DFS.

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

Править: Расширьте это описание немного

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

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

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

Править: Забыл это: И если Вы удаляете последнее, освещенное от узла в наборе, пересекаете края и удаляете узел Вы просто "неосвещенный" от их набора (и возможно пересекаете оттуда также, и так далее),

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

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

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

Затем в узле Вы сохранили бы это, это был источник (и таким образом осветил отдельно), и и в B и в C, который Вы сохраните, они были освещены A, и в D Вы сохраните это, это было освещено и A и C.

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

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

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