Skip to content

Instantly share code, notes, and snippets.

@BetelGeuseee
Created September 8, 2020 12:23
Show Gist options
  • Save BetelGeuseee/3485bf93bafda1b1869916fc2477c829 to your computer and use it in GitHub Desktop.
Save BetelGeuseee/3485bf93bafda1b1869916fc2477c829 to your computer and use it in GitHub Desktop.
Depth First Search in Graph using JAVA (modified code from gfg)
package GraphProblems;
import java.util.Iterator;
import java.util.LinkedList;
class Graph{
private int vertices;
private LinkedList<Integer>[] adjacent;
Graph(int v){
this.vertices=v;
adjacent=new LinkedList[v]; //makes vertices array
for(int i=0;i<v;i++){
adjacent[i]=new LinkedList<>(); //adjacent[0],adjacent[1],adjacent[2]...these are vertices
}//adjacent[0] refers to the new linkedlist object so on and so forth
}
public void addEdge(int v,int w){
adjacent[v].add(w);//this will add edges to the vertices/node
}
public void visitedVerticesTracker(int v,boolean[] visVertices){
visVertices[v]=true;
System.out.print(v+" ");
Iterator<Integer> i =adjacent[v].listIterator();
while(i.hasNext()){
int n = i.next();
if(!visVertices[n]){
visitedVerticesTracker(n,visVertices);//recursive call for all the vertices adjacent to this vertex
}
}
}
public void depthFirstSearch(int v){
boolean visitedVertices[] = new boolean[vertices];
visitedVerticesTracker(v,visitedVertices);
}
}
public class DepthFirstSearchGraph {
public static void main(String[] args) {
Graph graph = new Graph(4); //making 4 vertices/nodes in graph
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,2);
graph.addEdge(2,0);
graph.addEdge(2,3);
graph.addEdge(3,3);
graph.depthFirstSearch(2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment