Question

In Java:

We say that a graph G is strongly-connected if, for every pair of vertices i and j in G, there is a path from i to j. Showhowtotest if G is strongly-connected in O(n + m) time. . Write a method and test it in Main. Explain why it is O(n+m).

Graph is directed

Answer 1

Dear Student,

1. It is correct that Graph is strongly connected if there is a path from i to j for every pair of vertices.

2. As you have mentioned that time complexity of the algorithm should be O(n+m) and I am considering n is no of vertices and m is no of edges.

3. To achieve this time complexity we must need to use Kosaraju's Algorithm which is used to find count of strongly connected components in a graph using DFS (Depth First Search) algorithm. If strongly connected component is 1 in our graph then we can say that graph is strongly connected.

4. Time complexity of Kosaraju's Algorithm is similar to DFS (Depth First Search) algorithm as we will use DFS inside Kosaraju's Alogorithm.

5. But wait there is a hack, If we store our graph in adjacency list data structure then only we will get complexity of O(n+m) while in adjacency matrix we will get O(n²) .

5. Kosaraju's Algorithm uses below steps to find connected component of graph:-

i) Mark all vertices as not visited.

ii) Perform DFS on the given graph and update visit flag of each vertex on every visit. If any of the vertex is marked as not visited after DFS it means that  another component is present in the graph. Hence the graph is not strongly connected.

iii) In the step 2 if all the vertices are marked as visited then reverse the graph.

iv) Mark all vertices of the reversed graph as not visited again.

v) Perform DFS again on the reversed graph and updated visit flag of each vertex on every visit. If any of the vertex is marked as not visited after DFS it means that  another component is present in the graph. Hence the graph is not strongly connected otherwise graph is strongly connected.

So, the summary is that for strongly connected graph the count of strongly connected component should be exactly one.

6. The screenshot of the Java Program for the indentation purpose to check whether graph is strongly connected or not is mentioned below:-

7. Java Program in Textual format for ready copying of the code is mentioned below:-

package HomeworkLib;

import java.util.Iterator;
import java.util.LinkedList;

public class StronglyConnectedGraph {

   // no of vertices
   private int N;

   //Linked List to store adjacency list
   private LinkedList<Integer> adj[];

   //Constructor to initialize the count of vertices and Linked List
   StronglyConnectedGraph(int n) {
       this.N = n;
       adj = new LinkedList[n];
       for (int i=0; i<n; ++i)
           adj[i] = new LinkedList<Integer>();
   }

   //It is initializing adjacent of v as w
   void addEdge(int v,int w) {
       adj[v].add(w);
   }

   //This is a recursive function to find DFS of the graph from source vertex v
   void findDFS(int v,Boolean visited[]) {
      
       //Mark as passed vertex as visited
       visited[v] = true;

       int n;

       //Find all the vertex adjacent to the vertex v
       Iterator<Integer> i = adj[v].iterator();
       while (i.hasNext()){
           n = i.next();
           if (!visited[n])
               findDFS(n,visited);
       }
   }

   //This function will transpose the graph or reverse the graph
   StronglyConnectedGraph getTranspose() {
       StronglyConnectedGraph g = new StronglyConnectedGraph(N);
       for (int v = 0; v < N; v++){
           // Computer reverse adjacent for all the vertices for the given vertex v
           Iterator<Integer> i = adj[v].listIterator();
           while (i.hasNext())
               g.adj[i.next()].add(v);
       }
       return g;
   }

   boolean isStronglyConnected(){

       //Step 1: Mark all the vertex as not visited
       Boolean visited[] = new Boolean[N];
       for (int i = 0; i < N; i++)
           visited[i] = false;

       /*
       * Step 2: Perform DFS on the given graph and update visit flag of each vertex
       * on every visit.
       */
       findDFS(0, visited);

       /*
       * If any of the vertex is marked as not visited after DFS it means that
       * another component is present in the graph. Hence the graph is not strongly
       * connected and return false
       */
       for (int i = 0; i < N; i++)
           if (visited[i] == false)
               return false;

       // Step 3: Reverse the graph if all the vertices in above step is marked as visited
       StronglyConnectedGraph gr = getTranspose();

       // Step 4: Marks all vertices as not visited in reverse graph
       for (int i = 0; i < N; i++)
           visited[i] = false;

       /*
       *Step 5: Perform DFS again on the reversed graph and updated visit flag of each
       * vertex on every visit.
       */
       gr.findDFS(0, visited);

       /* If any of the vertex is marked as not visited after
       * DFS it means that  another component is present in the graph. Hence the
       * graph is not strongly connected and return false otherwise graph is strongly connected return true
       */
       for (int i = 0; i < N; i++)
           if (visited[i] == false)
               return false;

       return true;
   }

   public static void main(String args[]) {
      
       //Creating graph for the figure1
       StronglyConnectedGraph firstGraph = new StronglyConnectedGraph(5);
       firstGraph.addEdge(0, 1);
       firstGraph.addEdge(1, 2);
       firstGraph.addEdge(2, 3);
       firstGraph.addEdge(3, 0);
       firstGraph.addEdge(2, 4);
       firstGraph.addEdge(4, 3);
       if (firstGraph.isStronglyConnected())
           System.out.println("Graph is strongly connected.");
       else
           System.out.println("No");

       //Creating graph for the figure2
       StronglyConnectedGraph secondGraph = new StronglyConnectedGraph(4);
       secondGraph.addEdge(0, 1);
       secondGraph.addEdge(1, 2);
       secondGraph.addEdge(2, 3);
       secondGraph.addEdge(3, 1);
       if (secondGraph.isStronglyConnected())
           System.out.println("Graph is strongly connected.");
       else
           System.out.println("Graph is not strongly connected.");
   }
}

8. Below screenshot showing the graphs used for checking connected components. In the main function two graphs is initialized using adjacency list which are below graphs only in pictorial representation:-

9. Output of the above graphs is mentioned below whether they are strongly connected or not:-

As we can see in the output that First graph is strongly connected while the second graph is not.

In the first graph we can reach from any vertex to any vertex.

In the second graph we can not reach from 3 to 0, 1 to 0 and 2 to 0. Hence this graph is not strongly connected.

10. Now coming to the question of time complexity:-

Time complexity of the Kosaraju's Algorithm depends on the DFS time complexity. The time complexity of the DFS is O(n+m) where n is no of vertices and m is no of edges. Hence in Kosaraju's we are using DFS twice hence the time complexity of Kosaraju's algorithm is 2*O(n+m) which is similar to O(n+m) only neglecting 2 in the expression.

Note:- 1. Time complexity of the DFS depends on the underlying data structure. As we are using adjacency list then only the time complexity of DFS will be O(n+m).

2. Time complexity of the DFS is O(n+m) because in worst case each vertex will be visited exactly once and each edge will be visited exactly once.

If you need further help please feel free to reach me through comments section.