Мне нужно проверить, сильно ли связан направленный граф, или, другими словами, если все узлы могут быть достигнуты любым другим node (не обязательно через прямое ребро).
Один из способов сделать это - запустить DFS и BFS на каждом node и увидеть, что все остальные доступны.
Есть ли лучший способ сделать это?
алгоритм сильно связанных компонентов Tarjan (или вариант Габова), конечно, будет достаточно; если имеется только одна сильно связанная компонента, то граф сильно связан.
Оба являются линейными.
Как и при первом поиске по нормальной глубине, вы отслеживаете статус каждого node: новый, видимый, но все еще открытый (он в стеке вызовов), и просматривается и завершается. Кроме того, вы сохраняете глубину, когда вы впервые достигли node, и самую низкую такую глубину, которая достижима из node (вы знаете это после завершения node). A node является корнем сильно связной компоненты, если самая низкая достижимая глубина равна собственной глубине. Это работает, даже если глубина, с которой вы достигаете node от корня, не является минимальной возможной.
Чтобы проверить, является ли весь граф единственным SCC, инициируйте dfs из любого единственного node, и когда вы закончите, если самая низкая достижимая глубина равна 0, и каждый node был посещен, тогда весь граф сильно связан.
Рассмотрим следующий алгоритм.
Начните с произвольной вершины v графика G и запустите a DFS(G, v).
Если DFS(G, v) не достигает любой другой вершины в графе G, то существует некоторая вершина u, такая, что нет ориентированного пути от v до u, и, таким образом, G не сильно связан.
Если он достигает каждой вершины, то существует ориентированный путь от v к каждой другой вершине графа G.
Обратное направление всех ребер в ориентированном графе G.
Снова запустите DFS, начиная с v.
Если DFS не достигает каждой вершины, то существует некоторая вершина u, такая, что в исходном графе нет ориентированного пути от u до v.
С другой стороны, если он достигает каждой вершины, то в исходном графе есть направленный путь от каждой вершины u до v.
Таким образом, если G "проходит" оба DFS, то оно сильно связано. Кроме того, поскольку DFS работает в O(n + m) времени, этот алгоритм работает в O(2(n + m)) = O(n + m) времени, так как он требует двух обходов DFS.
Вы можете вычислить "Все-парный короткий путь" и посмотреть, нет ли бесконечного.
Тарьянский алгоритм уже упоминался. Но я обычно нахожу алгоритм Косараджу легче следовать, хотя ему нужны два обхода графика. 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
}
Одним из способов сделать это было бы создание матрицы Лапласа для графика, затем вычисление собственных значений и, наконец, подсчет числа нули. Граф является сильно связным, если существует только одно нулевое собственное значение.
Примечание. Обратите внимание на несколько иной метод создания матрицы Лапласа для ориентированных графов.