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

Question

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

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

Есть ли лучший способ сделать это?

Answer 1

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

---

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.

Answer 2

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

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

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

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

Answer 3

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

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]. В SCC d[v] <= d[u] <= d[v], таким образом, все узлы в SCC будут иметь одинаковую глубину. Чтобы определить, является ли граф SCC, мы проверяем, все ли узлы имеют одинаковый d[i].

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

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

Answer 4

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
}

Answer 5

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

Answer 6

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

Answer 7

Вы можете использовать простой алгоритм 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. В противном случае верните true.

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

Answer 8

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

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