Check if a given path exists in a graph

Question

I'm using BFS to see if a given path exists in a graph:

static class Node{
 int data;
 Node next;
 public Node(int data){
 this.data = data;
 }
}
//Adjency List to store the reference to head of each Node/Vertice
static class AdjList implements Iterable<Integer>{
 Node head;
 public void add(int to){
 if(head==null){
 head = new Node(to);
 }else{
 Node temp = head;
 while(temp.next!=null)
 temp = temp.next;
 temp.next = new Node(to);
 }
 }
 //Used to iterate over the adjacency list while BFS
 @Override
 public Iterator<Integer> iterator(){
 Iterator<Integer> it = new Iterator<Integer>(){
 Node temp = head;
 @Override
 public boolean hasNext(){
 return temp!=null;
 }
 @Override
 public Integer next(){
 Node toRet = temp;
 temp = temp.next;
 return toRet.data;
 }
 @Override
 public void remove(){
 throw new UnsupportedOperationException();
 }
 };
 return it;
 }
}
static class Graph{
 AdjList[] lists;
 int numberOfNodes;
 public Graph(int numberOfNodes){
 lists = new AdjList[numberOfNodes];
 this.numberOfNodes = numberOfNodes;
 for(int i=0; i<numberOfNodes; i++){
 lists[i] = new AdjList();
 }
 }
 //Adds edge from/to vertice
 public void addEdge(int from, int to){
 lists[from].add(to);
 }
 public boolean BFS(int from, int to){
 LinkedList<Integer> queue = new LinkedList<>();
 queue.add(from);
 boolean[] visited = new boolean[numberOfNodes];
 visited[from]= true;
 while(!queue.isEmpty()){
 if(visited[to]==true)
 return true;
 int curr = queue.poll();
 System.out.print(curr + " ");
 Iterator<Integer> iter = lists[curr].iterator();
 while(iter.hasNext()){
 int currVal = iter.next();
 if(visited[currVal]==false){
 queue.add(currVal);
 visited[currVal]=true;
 }
 }
 }
 return false; 
 }
}
public static void main(String[] args) {
 Graph myGraph = new Graph(3);
 myGraph.addEdge(0, 1);
 myGraph.addEdge(1,2);
 myGraph.addEdge(2,1);
 System.out.println("Path from 2 to 0 exists : " + Boolean.valueOf(myGraph.BFS(2,0)));
}

I could've used DFS for the same purpose which requires lesser memory than BFS, but since my Graph was pretty small, it wouldn't have made much of a difference. Apart from that, under what circumstances should I prefer either of them?

• coderodde: DFS may be more memory-efficient, that's true. However, if your graph is large, there is risk that DFS will recur too deep and cause stack overflow.

Answer 1

Regarding the code, I'd have only 2 suggestions:

• Use brackets even for single-line ifs. It improves readability and makes the code less error prone.
• Try not to shorten member names too much (like iter or it for example). It improves readability.

As for the chosen algorithm and possible alternative I'd suggest Iterative Deepening DFS. It has the best of both Depth-First Search and Breadth-First Search - it's complete, finds the optimal solution, and doesn't use too much space.

Let me know if anything's unclear.