2
$\begingroup$

I'm having a difficult time explaining/understanding a (seemingly) simple argument of an algorithm that I know I can use to determine if a directed graph G is strongly connected.

The algorithm that I know (does this have a name?) goes like this:

Use BFS (breadth-first-search) on G staring from some node S
   IF every node is found
       Construct G^ (G with reversed Edges, G transpose?)
       Use BFS on G^ starting from the same node S
       IF every node is found
          G is strongly connected
       ELSE
          G is not strongly connected
   ELSE
      G is not strongly connected
End

So the first run of BFS ensures that the node S can reach every other node on G, which makes sense. If it cant, then clearly G is not strongly connected.

The second run of BFS on G^, as I understand, will show that any node on the graph can also make it to S in G. This is the part I can't fully explain to myself.

The conclusion of the algorithm I understand, if S can make it to every node and every node can make it to S, then any two nodes will always be able to make it to each other through S.

To reiterate my question, I'm looking for an explanation on why determining S can make it to every node in G^ shows that every node can make it to S in G. I've tried doing a proof by contradiction, but I'm having a hard time wording it out. Any explanation will help me. Thank you!

$\endgroup$
1
$\begingroup$

When you do a BFS starting at a node $S$ of a directed graph, the neighbors of $S$ in the BFS tree would be the out-neighbors of $S$ (not the in-neighbors). The resulting BFS tree tells you the shortest directed path from $S$ to all other nodes. The important observation here is that BFS on a digraph considers only the outgoing arcs from each vertex. So if you want to determine whether there is a directed path from some other node $T$ to $S$, you need to do a BFS rooted at $T$.

Alternatively, you can reverse the direction on each arc of the directed graph and perform a BFS rooted at $S$. There is a directed path from $T$ to $S$ in the given digraph if and only if there is a directed path from $S$ to $T$ in the reverse digraph. This should be clear from small examples, but a formal proof can be given: if $(x_0,x_1), (x_1,x_2), \ldots, (x_{k-1},x_k)$ is a directed path from $S$ to $T$ in the reverse digraph, then $(x_k,x_{k-1}),\ldots,(x_1,x_0)$ is a directed path from $T$ to $S$ in the given digraph. In other words, rather than do a BFS on the digraph starting from node $T$, do a BFS on the reverse digraph starting from node $S$. The latter approach requires only a second BFS on the reverse digraph starting from $S$ rather than a BFS starting from every other node on the given digraph.

You can think of the second BFS starting from $S$ as being a BFS on the original graph itself (not the reverse graph), but with the BFS implemented by choosing neighbors based on incoming arcs (rather than outgoing arcs).

$\endgroup$
  • 1
    $\begingroup$ Thank you this is exactly what I was looking for. Particularly the summation at the end made everything click for me. "You can think of the second BFS starting from SS as being a BFS on the original graph itself (not the reverse graph), but with the BFS implemented by choosing neighbors based on incoming arcs (rather than outgoing arcs)." $\endgroup$ – Markov Sep 5 '16 at 22:11
0
$\begingroup$

I think the analysis is simple if the starting note $S$ for the second run of BFS is the same as the starting node of the first run.

The first run tells you that every node can be reached from $S$; the second run tells you every node can reach $S$. Combining these two facts shows strong connectivity: you can start from any node, go to $S$, and then go to any other node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.