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

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

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

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

Источник

9 ответов

Решение

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

Оба являются линейным временем.

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

Чтобы проверить, является ли весь граф одним 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 "проходит" обе DFS, это сильно связано. Кроме того, поскольку 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 также отлично работает с правилом сокращения d[i] = min(d[j]) Вот.

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])

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

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

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

Источник 
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
}
Источник

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

Источник

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

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

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

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

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

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

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

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

Источник

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

Источник

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

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

Источник

Алгоритм проверки сильно связности графа довольно прост. Но почему приведенный ниже алгоритм работает?

Алгоритм: предположим, что есть граф с вершинами [A, B, C......Z]

  1. Выберите любой случайный узел, скажем J, и выполните из него поиск в глубину. Если все узлы доступны, перейдите к шагу 2.

  2. Измените направления ребер графа, выполнив транспонирование.

  3. Снова запустите DFS с узла J и проверьте, все ли узлы посещены. Если да, то граф сильно связан и возвращает true.

Выполнение шага 1 имеет смысл, потому что мы должны проверить, можем ли мы достичь всех узлов из этого узла. После этого следующим логическим шагом может быть

i) Теперь сделайте это для всех остальных узлов

ii) или попытаться связаться с узлом J из любого другого узла. Потому что, достигнув узла J, вы уверены, что сможете добраться до любого другого узла благодаря шагу 1.

Это то, что мы пытаемся сделать на шагах 2 и 3. Если в транспонированном графе узел J может достигать всех других узлов, то это означает, что в исходном графе все остальные узлы могут достигать J.

Источник
Другие вопросы по тегам