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 verticesprivate LinkedList < Integer > adjacencyList[]; //Adjacency Lists@SuppressWarnings("unchecked")// ConstructorGraph(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 graphvoid 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 ...