Created
September 8, 2020 12:23
-
-
Save BetelGeuseee/3485bf93bafda1b1869916fc2477c829 to your computer and use it in GitHub Desktop.
Depth First Search in Graph using JAVA (modified code from gfg)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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