BFS_DFS_recursive

// "static void main" must be defined in a public class. import java.util.* ; import java.io.*; public class Main { int Vertices ; List<List<Integer>> graph ; Main(int v){ this.Vertices = v ; this.graph = new ArrayList<>(this.Vertices) ; for(int i = 0 ; i < this.Vertices ;i++){ this.graph.add(new ArrayList<>()); } } public void addEdges(int source,int destination){ if(source <= this.Vertices && destination <= this.Vertices) this.graph.get(source).add(destination); else System.out.println("Invalid vertices"); } public void printGraph(){ for(int i= 0 ; i< this.graph.size() ;i++){ System.out.println("Vertex "+i); System.out.println("Edges"); for(Integer temp : graph.get(i)){ System.out.println("edges from vertex "+ i +"are "+temp); } } } public static void main(String[] args) { Main main = new Main(6); main.addEdges(0,1); main.addEdges(0,2); main.addEdges(1,3); main.addEdges(2,4); main.addEdges(3,2); main.addEdges(4,2); main.addEdges(3,1); main.addEdges(1,5); main.printGraph(); //System.out.println(main.hasPathDFS(0,5)); System.out.println(main.hasPathBFS(0,5)); } public boolean hasPathDFS(int source,int destination){ HashSet<Integer> visited = new HashSet<>() ; return DFS(source,destination,visited); } public boolean DFS(int source,int destination,HashSet <Integer> visited){ if(visited.contains(source)) return false ; visited.add(source); if(source == destination) return true ; // check for its children System.out.println(source); for(Integer edges: this.graph.get(source)){ // check if children have a path if(DFS(edges,destination,visited)){ return true ; } } return false ; } public boolean hasPathBFS(int source, int destination){ HashSet<Integer> visited = new HashSet<>() ; PriorityQueue <Integer> pq = new PriorityQueue<>() ; pq.add(source); while(!pq.isEmpty()){ int node = pq.poll(); if(node == destination) return true ; if(visited.contains(node)) continue ; System.out.println(node); visited.add(node); // check its children for(Integer child: this.graph.get(node)){ pq.add(child); } } return false ; } }