//Note - for disconnected graph use the approach for checking connected components.
package project0;
import java.util.LinkedList;
class Graph {
private int v; //total number of vertices
private LinkedList adj[]; //adjacency list
private boolean visited[]; //to keep track of the node which are visited.
Graph(int v) {
this.v = v;
this.adj = new LinkedList[v];
this.visited = new boolean[v];
for (int i = 0; i < this.v; i++) {
adj[i] = new LinkedList();
this.visited[i] = false;
}
}
public void addEdge(int u, int v) { // edge from u -> v
this.adj[u].add(v);
}
public void DFS(int source) {
//if the node is already visited, then backtrack.
if (this.visited[source] == true) {
return;
}
//mark the source vertex as visited
System.out.print(source + " ");
this.visited[source] = true;
//traverse through all the neighbours and backtrack if already visited.
LinkedList neighbours = this.adj[source];
for (int next : neighbours) {
DFS(next);
}
}
}
public class Main {
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
}
}