Алгоритм проверки того, является ли ориентированный граф сильно связным

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

Вопрос

Мне нужно проверить, является ли ориентированный граф сильно связанный, или, другими словами, если все узлы могут быть достигнуты любым другим узлом (не обязательно через прямое ребро).

Один из способов сделать это - запустить DFS и BFS на каждом узле и убедиться, что все остальные по-прежнему доступны.

Есть ли лучший подход для этого?

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

Решение

У Тарьяна алгоритм сильно связанных компонентов (или Габоу вариации), конечно, будет достаточно;если есть только один сильно связанный компонент, то граф сильно связан.

И то, и другое - линейное время.

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

Чтобы просто проверить, является ли весь график одним SCC, запустите dfs с любого отдельного узла, и когда вы закончите, если наименьшая достижимая глубина равна 0, и каждый узел был посещен, то весь график сильно связан.

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

Рассмотрим следующий алгоритм.

  1. Начинайте со случайной вершины v из графика G, и запустить DFS(G, v).

    • Если DFS(G, v) не удается достичь ни одной другой вершины в графе G, тогда есть некоторая вершина u, такой , что нет направленного пути от v Для u, и таким образом G является не сильно связанный.

    • Если он достигает каждой вершины, то существует направленный путь от v к любой другой вершине графа G.

  2. Измените направление всех ребер в ориентированном графе на обратное G.

  3. Снова запустите DFS начиная с v.

    • Если DFS не удается достичь каждой вершины, значит, есть какая-то вершина u, такой , что в исходном графе нет направленного пути из u Для v.

    • С другой стороны, если он действительно достигает каждой вершины, то в исходном графе из каждой вершины существует направленный путь u Для v.

Таким образом, если G "пропускает" оба DFSs, то он сильно связан.Кроме того, поскольку DFS работает в O(n + m) время, когда этот алгоритм выполняется в O(2(n + m)) = O(n + m) время, так как для этого требуется 2 обхода DFS.

Чтобы проверить, есть ли у каждого узла оба пути к любому другому узлу в данном графе и от него:

1. DFS / BFS со всех узлов:

Алгоритм Тарьяна предполагает, что каждый узел имеет глубину d[i]. Изначально корень имеет наименьшую глубину. И мы делаем обновления DFS после заказа d[i] = min(d[j]) для любого соседа j из i. На самом деле BFS также прекрасно работает с правилом сокращения u здесь. 

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

Если есть путь переадресации от v до d[u] <= d[v], то d[v] <= d[u] <= d[v]. Таким образом, в SCC <=> все узлы в SCC будут иметь одинаковую глубину. Чтобы определить, является ли граф SCC, мы проверяем, все ли узлы имеют одинаковый <=>.

2. Две DFS / BFS с одного узла:

Это упрощенная версия Косараю & # 8217; алгоритм s . Начиная с корня, мы проверяем, может ли каждый узел быть доступен с помощью DFS / BFS. Затем поменяйте направление каждого ребра. Мы проверяем, можно ли снова получить доступ к каждому узлу из того же корня. См. код C ++ .

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

Алгоритм Тарьяна уже упоминался. Но я обычно нахожу Алгоритм Косараю более легким для понимания, даже если ему требуется два обхода графа , IIRC, это также довольно хорошо объяснено в CLRS. 

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Один из способов сделать это - создать матрицу Лапласа для графа, затем вычислить собственные значения и, наконец, посчитать количество нулей. Граф является сильно связным, если существует только одно нулевое собственное значение.

Примечание. Обратите внимание на несколько иной способ создания матрицы Лапласа для ориентированных графов.

Вы можете использовать Kosaraju & # 8217; простой алгоритм на основе DFS, который выполняет два обхода графа DFS:

Идея состоит в том, что если каждый узел может быть достигнут из вершины v, а каждый узел может достичь v, то граф сильно связен. На шаге 2 алгоритма мы проверяем, достижимы ли все вершины из v. На шаге 4 мы проверяем, могут ли все вершины достичь v (В обратном графе, если все вершины достижимы из v, все вершины могут достичь v в оригинале. график).

Алгоритм: 1) Инициализировать все вершины как не посещенные.

2) Выполните обход графа DFS, начиная с любой произвольной вершины v. Если обход DFS не & # 8217; t посещение всех вершин, верните false.

3) Инвертировать все дуги (или найти транспонирование или реверс графика)

4) Пометить все вершины как не посещенные в обратном графе.

5) Выполните обход DFS по обращенному графу, начиная с той же вершины v (То же, что в шаге 2). Если обход DFS не & # 8217; t посещает все вершины, верните false. В противном случае верните true.

Сложность по времени. Сложность по времени в приведенной выше реализации такая же, как Поиск в глубину, который равен O (V + E), если граф представлен с использованием представления списка смежности.

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