Graph: Find if a path exists between two nodes using breadth first search (bfs) approach


Write a program to check if a path exists between two nodes in a graph using breadth first search (bfs) technique

 
Java Code
    import java.io.*;
    import java.util.*;
    
    class GraphCheckPathBFS{
    
        private HashSet visitedTracking = new HashSet();
        private LinkedList queue = new LinkedList();
    
        static class Node{
            private int id;
            LinkedList adjacent = new LinkedList();
    
            private Node(int id){
                this.id = id;
            }
    
        }
    
     
        //Function to add an edge into the graph
        public void addEdge(Node a, Node b)
        {
            a.adjacent.add(b);
            b.adjacent.add(a); 
        }
    
        public boolean hasPathUsingBFS(Node source, Node destination){
    
            if(source == null || destination == null) { return false; }
            visitedTracking.add(source.id);
            queue.add(source);
    
            while(!queue.isEmpty()){
    
                Node curr = queue.remove();
                if(curr == destination){ return true;}
    
                for(Node child : curr.adjacent){
                    if(!visitedTracking.contains(child.id)){
                        visitedTracking.add(child.id);
                        queue.add(child);
                    }
                }
            }
    
            return false;
    
        }
    
    
        public static void main(String args[]){
    
            GraphCheckPathBFS gS = new GraphCheckPathBFS();
            
            Node a1 = new Node(1);
            Node a2 = new Node(2);
            Node a3 = new Node(3);
            Node a4 = new Node(4);
            Node a7 = new Node(7);
            Node a9 = new Node(9);
            Node a12 = new Node(12);
            Node a5 = new Node(5);
            Node a8 = new Node(8);
            Node a6 = new Node(6);
    
            gS.addEdge(a1,a9);
            gS.addEdge(a1,a3);
            gS.addEdge(a1,a4);
            gS.addEdge(a3,a7);
            gS.addEdge(a7,a2);
            //gS.addEdge(a2,a4);
            gS.addEdge(a2,a6);
            gS.addEdge(a4,a5);
            gS.addEdge(a4,a12);
            gS.addEdge(a6,a8);
        
            System.out.println("Using BFS there exists path between nodes 3 & 12: " + 
                 gS.hasPathUsingBFS(a3,a12));
    
        }
  }
 
Output

Using BFS there exists path between nodes 3 & 12: true



Thanks for feedback.



Read More....
Find all possible paths in a graph from given source to destination nodes
Find all paths in a graph using DFS recursive
Find if a path exists between two nodes in a graph using DFS recursive