Я ищу эффективный алгоритм, чтобы определить, будет ли удаление набора узлов в графе разбивать граф на несколько компонентов.
Формально, учитывая неориентированный граф G = (V, E) и непустой набор вершин W ⊆ V , возврат true тогда и только тогда W - набор вершин. В графе нет граничных весов.
То, что до сих пор приходит мне в голову, использует несвязанное множество :
- Несвязанное множество инициализируется всеми соседями узлы в W , где каждый набор содержит одного такого соседа.
- Во время первого обхода всех узлов V \ W для каждого вновь исследованного узла выполняется ровно один из следующих случаев X :
- X уже находится в том же наборе, что и его предшественник
- X отсутствует в непересекающемся наборе ⇒ добавляется в тот же набор, что и его предшественник (оба случая означают, что подключенный компонент дальнейшее изучение)
- X находится в другом наборе ⇒ объединить непересекающиеся множества (два компонента до сих пор выглядели как отключенные, но оказались подключенными)
- Всякий раз, когда непересекающийся набор содержит только один набор (даже до завершения обхода), результат равен
false. - Если непересекающийся набор содержит 2 или более наборов по окончании обхода, результат равен
true.
Сложность по времени равна O (| V | + | E |) (при условии, что сложность по времени непересекающегося множества равна O (1) вместо более точной обратная функция Аккермана).
Знаете ли вы лучшее решение (или с ee есть какой-либо недостаток в предложенном)?
Примечание. Поскольку это часто встречается в результатах поиска Google, я хотел бы прямо заявить, что не ищу алгоритм для поиска пока неизвестного набора срезов вершин, не говоря уже об оптимальном. Задан набор вершин, задача состоит в том, чтобы просто сказать да или нет.
Примечание 2: Кроме того, я не ищу проверку набора срезов кромок (мне известно о Найти набор срезов в график , но не могу придумать подобное решение для вершин).
Спасибо!
ОБНОВЛЕНИЕ: Я понял, что в случае true результат Мне также понадобятся данные узлов в отключенных компонентах в иерархической структуре в зависимости от расстояния от удаленных узлов. Отсюда и выбор БФС. Я прошу прощения за постредактирование.
Практический случай позади - сбой в телекоммуникационной сети. Когда некоторые узлы ломаются, и вся сеть отключается, один компонент (содержащий узел с подключением к сети более высокого уровня) все еще в порядке, о всех других компонентах необходимо сообщать.