Question

Let G be a directed graph. In class, we saw an algorithm that uses the information obtained from a DFS to determine the strongly connected components of G. Make an argument for why using instead BFS will not work. Namely, focus on why the order in which we visit vertices in a BFS does not give us any information about the strongly connected component structure in G (note a BFS does not label vertices with pre and post values, so in your argument, just work with the order in which vertices are dequeued from the BFS queue).

Answer 1

Strongly Connected Components

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

We can find all strongly connected components in O(V+E) time using Kosaraju’s algorithm.

Following is detailed Kosaraju’s algorithm(DFS based).

• Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack.
• Reverse directions of all arcs to obtain the transpose graph.
• One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS(v). The DFS starting from v prints strongly connected component of v.

How does this work?

The above algorithm is DFS based. It does DFS two times. DFS of a graph produces a single tree if all vertices are reachable from the DFS starting point. Otherwise DFS produces a forest. So DFS of a graph with only one SCC always produces a tree. The important point to note is DFS may produce a tree or a forest when there are more than one SCCs depending upon the chosen starting point.

In the next step, we reverse the graph. In the reversed graph, the edges that connect two components are reversed. So if we do a DFS of the reversed graph using sequence of vertices in stack, we process vertices from sink to source (in reversed graph). That is what we wanted to achieve and that is all needed to print SCCs one by one.

Kosaraju’s BFS based simple algorithm also work on the same principle as DFS based algorithm does.

We can also use BFS based Kosaraju's algorithm for getting the Strongly connectd components.

We don't need the order in which it visits the vertices. We just want to know how many vertices and what are all those vertices we can reach by starting traversal from this location. This can be achieved by DFS or BFS as both are graph traversal algorithms and both can do this task.

Following is Kosaraju’s BFS based simple algorithm that does two BFS traversals of graph:

• Initialize all vertices as not visited.
• Do a BFS traversal of graph starting from any arbitrary vertex v. If BFS traversal doesn’t visit all vertices, then return false.
• Reverse all edges (or find transpose or reverse of graph) Mark all vertices as not visited in reversed graph.
• Again do a BFS traversal of reversed graph starting from same vertex v (Same as step 2). If BFS traversal doesn’t visit all vertices, then return false. Otherwise, return true.