Algorithm to check if directed graph is strongly connected

Question

I need to check if a directed graph is strongly connected, or, in other words, if all nodes can be reached by any other node (not necessarily through direct edge).

One way of doing this is running a DFS and BFS on every node and see all others are still reachable.

Is there a better approach to do that?

Horseshoes

I believe the commonly accepted name is "directed graph", not "directional graph". – Lanti

Answer 1

Tarjan's strongly connected components algorithm (or Gabow's variation) will of course suffice; if there's only one strongly connected component, then the graph is strongly connected.

Both are linear time.

As with a normal depth first search, you track the status of each node: new, seen but still open (it's in the call stack), and seen and finished. In addition, you store the depth when you first reached a node, and the lowest such depth that is reachable from the node (you know this after you finish a node). A node is the root of a strongly connected component if the lowest reachable depth is equal to its own depth. This works even if the depth by which you reach a node from the root isn't the minimum possible.

To check just for whether the whole graph is a single SCC, initiate the dfs from any single node, and when you've finished, if the lowest reachable depth is 0, and every node was visited, then the whole graph is strongly connected.

Incidental

Answer 2

Consider the following algorithm.

---

1. Start at a random vertex v of the graph G, and run a DFS(G, v).

   • If DFS(G, v) fails to reach every other vertex in the graph G, then there is some vertex u, such that there is no directed path from v to u, and thus G is not strongly connected.

   • If it does reach every vertex, then there is a directed path from v to every other vertex in the graph G.

2. Reverse the direction of all edges in the directed graph G.

3. Again run a DFS starting at v.

   • If the DFS fails to reach every vertex, then there is some vertex u, such that in the original graph there is no directed path from u to v.

   • On the other hand, if it does reach every vertex, then in the original graph there is a directed path from every vertex u to v.

Thus, if G "passes" both DFSs, it is strongly connected. Furthermore, since a DFS runs in O(n + m) time, this algorithm runs in O(2(n + m)) = O(n + m) time, since it requires 2 DFS traversals.

Democritus

Nice! Very similar to Kosaraju's algorithm to find strongly connected components. – Amygdalin

@Alip - Two queries: (1)Can we use BFS(G, v) instead of DFS(G,v) for your algorithm? (2)To evaluate if DFS reaches every vertices from v, can we keep a count c of visted vertices and then just compare if c == |G.V|? – Tammy

Answer 3

To check if every node has both paths to and from every other node in a given graph:

1. DFS/BFS from all nodes:

Tarjan's algorithm supposes every node has a depth d[i]. Initially, the root has the smallest depth. And we do the post-order DFS updates d[i] = min(d[j]) for any neighbor j of i. Actually BFS also works fine with the reduction rule d[i] = min(d[j]) here.

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

If there is a forwarding path from u to v, then d[u] <= d[v]. In the SCC, d[v] <= d[u] <= d[v], thus, all the nodes in SCC will have the same depth. To tell if a graph is a SCC, we check whether all nodes have the same d[i].

2. Two DFS/BFS from the single node:

It is a simplified version of the Kosaraju’s algorithm. Starting from the root, we check if every node can be reached by DFS/BFS. Then, reverse the direction of every edge. We check if every node can be reached from the same root again. See C++ code.

Outlawry

Answer 4

You can calculate the All-Pairs Shortest Path and see if any is infinite.

Lens

It could be, but there are definitely more efficient methods here. – Oldcastle

Answer 5

Tarjan's Algorithm has been already mentioned. But I usually find Kosaraju's Algorithm easier to follow even though it needs two traversals of the graph. IIRC, it is also pretty well explained in CLRS.

Mcfall

Answer 6

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
}

Unplug

Answer 7

You can use Kosaraju’s DFS based simple algorithm that does two DFS traversals of graph:

The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 2 of the algorithm, we check if all vertices are reachable from v. In step 4, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph).

Algorithm : 1) Initialize all vertices as not visited.

2) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.

3) Reverse all arcs (or find transpose or reverse of graph)

4) Mark all vertices as not-visited in reversed graph.

5) Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise return true.

Time Complexity: Time complexity of above implementation is same as Depth First Search which is O(V+E) if the graph is represented using adjacency list representation.

Penitential

Answer 8

One way of doing this would be to generate the Laplacian matrix for the graph, then calculate the eigenvalues, and finally count the number of zeros. The graph is strongly connection if there exists only one zero eigenvalue.

Note: Pay attention to the slightly different method for creating the Laplacian matrix for directed graphs.

Oldcastle

Answer 9

The algorithm to check if a graph is strongly connected is quite straightforward. But why does the below algorithm work?

Algorithm: suppose there is a graph with vertices [A, B, C......Z]

1. Choose any random node, say J, and perform DFS from it. If all the nodes are reachable then continue to step 2.

2. Reverse the directions of the edges of the graph by doing transpose.

3. Again run DFS from node J and check if all the nodes are visited. If yes then the graph is strongly connected and return true.

Performing step 1 makes sense because we have to check if we can reach all the nodes from that node. After this, next logical step could be

i) Now do this for all other nodes

ii) or try to reach node J from every other node. Because once you reach node J, you are sure that you can reach every other node because of step 1.

This is what we are trying to do in steps 2 & 3. If in a transposed graph node J is able to reach all other nodes then this implies that in original graph all other nodes can reach J.

Musk