Graph: Find if a path exists between two nodes using depth first search (dfs) recursive approach


Write a program to find if a path exists between two nodes in a graph using depth first search and recursion technique.

A path exists between two nodes if you can traverse from one node to other node via other nodes

 
Java Code
import java.io.*;
    import java.util.*;
    
    class GraphCheckPathDFS{
        
        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 hasPathUsingDFS(Node source, Node destination){
            if(source == null || destination == null) { return false; }
            
            visitedTracking.add(source.id);
            if(source == destination){ return true;}
    
            for(Node child : source.adjacent){
                if(!visitedTracking.contains(child.id)){
                    if(hasPathUsingDFS(child, destination)){
                        return true;
                    }
                }
            }
            return false;
        }
    
    
        public static void main(String args[]){
    
            GraphCheckPathDFS gS = new GraphCheckPathDFS();
            
            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 DFS there exists path between nodes 4 & 8: " + 
            gS.hasPathUsingDFS(a4,a8));
    
        }
  }
 
Output

Using DFS there exists path between nodes 4 & 8: 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 using breadth first search - BFS