How to determine if the directed graph is a strongly connected graph or not by using BFS algorithm?

Question

I have the following directed graph:

I was trying to determine if the above graph is a strongly connected graph or not.
I read in few communities that you can do this by following the steps below:

1. Take the BFS or DFS of the original graph.
2. Take a transpose of the original graph.
3. Take the BFS or DFS of the transpose.
4. If all the vertices from original graph were covered in both steps 1 & 3 then one can conclude that the graph is a strongly connected graph.

To solve this, I took the BFS of the original graph which gives me the output: 0 2 1 3 4

Then I reversed the edges of the original graph to get the transpose:

This is where I'm stuck. I have a few doubts here:

1. What is the BFS of this transpose? I'm stuck at the output: 0 1 2. Is this correct?

2. Can I conclude that the original graph is a weakly connected graph?

3. Can weakly connected graphs contain strongly connected components?

---

P.S: I've gone through the theories but can't seem to figure this out. Any help with examples would be much appreciated.

Answer 1

1. Yes, it is (assuming you start in 0, 1 or 2) - other vertices are unreachable from them. By the way, to make sure your algorithm for strong connectivity is correct, you have to start both BFS from the same vertex.

2. Yes, you can, because from first step you know that you can reach all vertices from vertex 0 even without traveling in reverse. Note that converse isn't true - even if both BFSes didn't visit all vertices, graph can still be weakly connected.

3. Of course. Any graph is disjoint union of strongly connected components.