В этой статье рассказывается об одном из наиболее полезных приложений DFS (поиск в глубину) для выявления уязвимостей в подключенной сети с целью создания надежной сетевой системы. Сегодня мы увидим, как DFS решает эту проблему.
Прежде чем перейти непосредственно к алгоритму, нам нужно понять несколько фундаментальных концепций графа.
Связанный граф. Связность в неориентированном графе означает, что каждая вершина может достичь любой другой вершины любым путем. Если график не связан, он может быть разбит на связанные компоненты. Точно так же граф, в котором каждая вершина не может достичь любой другой вершины по любому пути, приводит к несвязному графу.
Точка сочленения (AP): не что иное, как вершина, которая действует как посредник между двумя вершинами. Это означает, что если мы удалим вершину AP из графа, связь между этими двумя вершинами будет полностью потеряна. Проще говоря, AP - это узел в графе, который при удалении разделяет граф на два разных несвязанных графа.
Мосты. Точно так же мост - это не что иное, как канал связи между точкой сочленения и ее дочерним элементом. Проще говоря, мост - это ребро между двумя разными подграфами, при удалении которого получаются отдельные графы.
Теперь, учитывая, что мы знаем, что такое точки сочленения и мосты. Оба термина помогают нам проверить данный сетевой граф / систему на наличие уязвимостей. Допустим, у нас есть постановка задачи, в которой мы должны проверить, есть ли в графе мосты. ИЛИ, другими словами, мы должны определить, есть ли в графе какие-либо критические соединения, которые могут привести к поломке / отключению системы.
Для этого мы можем добиться этого, просто выполнив описанные выше шаги, которые мы обсуждали ранее.
Шаг 1. Поочередно удалите ребро с графика.
Шаг 2: после удаления ребра из графа выполните обход [DFS] по графу и посмотрите, все ли вершины посещены. Если какая-либо вершина остается непосещенной, то ребро, вызывающее проблему, является не чем иным, как критическим соединением.
временная сложность вышеупомянутого подхода составляет O (E * (V + E)), где (V + E) - для обхода графа. Поскольку мы должны выполнять DFS на каждом шаге после удаления края. Следовательно, это O (E * (V + E))
Есть лучшее решение, которое называется «алгоритм Тарьяна». Вы можете сослаться на то же самое в приведенной ниже ссылке
