Поскольку термин «мосты» звучит как соединение между двумя островами, которое играет важную роль в транспортировке и сообщении между двумя островами, точно так же мосты в неориентированном графе G (U, V) - это ребра, которые при удалении с графика увеличивается количество связанных компонентов. Другими словами, если мы удалим ребра, которые являются мостами, граф перестанет оставаться связным. Итак, как найти мосты в неориентированном графе?

В поисках мостов

Подход грубой силы для поиска мостов в неориентированном графе заключается в проверке каждого ребра, является ли оно мостом или нет. Этого можно достичь, сначала удалив ребро, а затем проверив, соединены ли еще вершины, которые соединены этим ребром, или нет. Но этот подход очень дорог с точки зрения количества операций, которые необходимо выполнить. Временная сложность для этого подхода равна O (E * (V + E)) (где E и V - количество ребер и вершин в графе G). Можем ли мы сделать лучше?

Ответ на этот вопрос - да, но как мы можем это сделать?

Давайте воспользуемся нашим знаменитым алгоритмом DFS, который работает с временной сложностью O (V + E), но прежде давайте разберемся, в чем основная идея поиска мостов. Для дерева DFS (которое мы получим при обходе графа с помощью DFS) заднее ребро - это ребро, которое соединяет вершину V с вершиной U, где U обнаруживается перед родителем вершины V.

Дерево DFS

Давайте разберемся с концепцией заднего ребра на примере графа, показанного на рис. 1. Здесь мы видим, что у нас есть ребра (2,4), (5,8), (1,3), (3,6) и ( 3,7) - мосты. Это потому, что, удаляя эти ребра, мы увеличиваем количество связанных компонентов. Давайте посмотрим на дерево DFS:

Мы можем видеть, что край (5,1) является задним краем, потому что, если мы запустим DFS с узла 1, мы пройдем и посетим узел 5 с узлом 2 в качестве родителя узла 5. Задний край находится от 5 до 1, где узел 1, который посещается до узла 2 (родитель узла 5), следовательно, это задний край. Почему же задним краям уделяется столько внимания? Это связано с тем, что задние края обеспечивают альтернативный путь. В этом примере, если мы удалим ребро (2,5), то ребро (1,5) будет альтернативным путем, и, следовательно, граф останется связным.

Предположим, что в DFS, пока мы ищем вершины, смежные с вершиной V, тогда (V, U) будет мостом тогда и только тогда, когда ни одна из вершин U или любой из ее потомков в дереве обхода DFS не имеет обратной стороны ребро к вершине V или любому из ее предков. Мы можем проверить существование задних ребер за O (V + E), поддерживая массив tin [], который сохранит отслеживать время, когда узел посещается впервые, мы также будем поддерживать массив low [] для каждой вершины V, который отслеживает время обнаружения самой ранней посещенной вершины, до которой текущая вершина V или любые вершины в поддереве с корнем V, у которых есть задний край, мы инициализируем low [] значением -1. Нам также понадобится одна переменная таймер, чтобы отслеживать текущее время обнаружения.

Для обновления low [] у нас есть 3 случая:

Теперь существует обратное ребро от U или одного из его потомков до предков V (V является родительским для U) тогда и только тогда, когда low [u] ≤ tin [v]. Вы можете подумать об этом на минуту и ​​получить объяснение. Это связано с тем, что если есть задний край, то значение low [u] должно быть меньше, чем tin [v]. Если low [u] = tin [v], то задний край идет непосредственно от V к U. Таким образом, ребро (v, u) в дереве DFS мост тогда и только тогда, когда low [u] ›tin [v].

Код для поиска мостов с помощью этой техники здесь:

В коде строка low [s] = min (low [s], low [x]) (после рекурсивного вызова dfs) ​​очень важна для распространения обновленного значения после того, как мы найдем задний край к родительским вершинам во время поиска с возвратом. Обратите внимание, что мы пропускаем родительские узлы, которые уже были посещены (if (x == p) continue;).

Поиск точек сочленения

Наконец, после долгого обсуждения мостов, давайте обсудим, что такое точки сочленения и как их найти в неориентированном графе. Точки сочленения - это вершины в неориентированном графе, которые при удалении вместе с соответствующими ребрами имеют тенденцию увеличивать количество связанных компонентов в графе. Например, вы можете рассматривать компьютерную сеть как График, то точки сочленения - это компьютеры, при удалении которых от сети сеть будет отключена или иным образом количество подключенных компонентов в сети увеличивается. Теперь мы можем найти точки сочленения так же, как и мосты, с очень незначительными изменениями в нашем алгоритме поиска мостов. На рис. 1 видно, что вершины 3,5,2 и 1 являются точками сочленения.

У нас есть два случая в алгоритме поиска точек сочленения:

  1. Для всех вершин, кроме корня в дереве DFS, если текущее ребро (V, U) таково, что ни одна из вершин U или его потомки имеют задний край по отношению к V или любому из предков V, тогда V является точкой сочленения. В противном случае V не является точкой сочленения.
  2. Если вершина, которую мы ищем, является корнем дерева DFS и если корень имеет не менее 2 дочерних элементов, то, удаляя корень и связанные с ним ребра, мы отсоединяем его дочерние элементы, и, следовательно, корень является точка сочленения. В противном случае корень не является точкой сочленения.

Для этого нам нужно немного изменить алгоритм, мы будем отслеживать родительские вершины во время обхода в дереве DFS, если родитель вершины = -1, то мы можем сказать, что это корень нашего дерева DFS и следовательно обрабатывайте соответственно. Второе, что нам нужно изменить, - это условие нахождения мостов в графе (low [u] ›tin [v], где v - родительский элемент u). В случае проверки того, является ли вершина точкой сочленения или нет, кроме корня, у нас есть условие low [u] ≥tin [v].

Это связано с тем, что если low [u] = tin [v], то задний край переходит непосредственно к v, иначе он переходит к предку v. В этом случае, если мы удаляем вершину v, тогда количество связных компонентов увеличивается, следовательно, это точка сочленения, но в случае моста, если мы имеем low [u] = tin [v], то если мы удалим ребро (v, u), граф все равно будет остаются связными, если заднее ребро исходит от потомков u, следовательно, ребро (v, u) не является мостом.

Вот код того же:

Если мы проследим код с входным графом, как показано на рис. 1, мы получим следующий результат в конце кода:

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

Итак, это конец статьи. Надеюсь, вам понравилось. Это моя первая статья на Medium. Итак, пожалуйста, если вы чувствуете необходимость в каких-либо улучшениях, вы можете посоветовать мне, я буду очень рад улучшить себя. Спасибо.