Determine if Graph has a Path


/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Graph { int Vertices ; List<List<Integer>> graph ; Graph(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 boolean hasPath(int source, int destination){ HashSet<Integer> visited = new HashSet<>(); return hasPathDFS(source,destination,visited); } public boolean hasPathDFS(int source,int destination,HashSet<Integer> visited){ if (!visited.contains(source)) { visited.add(source); System.out.print(source + " " ); if(source == destination) return true ; else { for(int e : this.graph.get(source)){ if(hasPathDFS(e,destination,visited)){ return true ; } } return false ; } } else{ return false ; } } public boolean hasPathDFSIterative(int source, int destination){ HashSet<Integer> visited = new HashSet<>(); Stack<Integer> stack = new Stack<>(); // Add it to the stack stack.push(source); while(!stack.isEmpty()){ } } public static void main (String[] args) throws java.lang.Exception { // your code goes here Graph g = new Graph(5); g.addEdges(0,1); g.addEdges(0,2); g.addEdges(1,3); g.addEdges(2,4); g.addEdges(3,2); g.addEdges(4,2); g.addEdges(3,1); g.addEdges(1,5); g.printGraph(); System.out.println(g.hasPath(0,5)); } }

Loading Please Wait...