...

/

Solution: Check if a Graph is Strongly Connected

Solution: Check if a Graph is Strongly Connected

This review provides a detailed analysis of the solution to check whether a graph is strongly connected or not.

We'll cover the following...

Solution

Press + to interact
main.java
Graph.java
import java.io.*;
import java.util.*;
class Graph {
private int vertices; //number of vertices
private LinkedList < Integer > adjacencyList[]; //Adjacency Lists
@SuppressWarnings("unchecked")
// Constructor
Graph(int vert) {
this.vertices = vert;
this.adjacencyList = new LinkedList[vertices];
for (int i = 0; i < this.vertices; ++i)
this.adjacencyList[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int source, int destination) {
this.adjacencyList[source].add(destination);
}
public int getVertices() {
return this.vertices;
}
public LinkedList < Integer > [] getAdj() {
return this.adjacencyList;
}
public Graph getTranspose() {
Graph g = new Graph(vertices);
for (int j = 0; j < vertices; j++) {
Iterator < Integer > i = adjacencyList[j].listIterator();
while (i.hasNext())
g.adjacencyList[i.next()].add(j);
}
return g;
}
};

Explanation

The solution might look confusing at first, but the logic behind it is pretty straight forward.

Start thinking about how graph traversal is implemented. All vertices are by default initialized as not visited, i.e., the values of visited are set to false (line 21). This is the same as in the depth-first graph traversal or the breadth-first graph traversal. You can start from any arbitrary vertex vv ...