Graph: Find all paths using depth first search recursive approach


Write a program to find all paths that exists between two given nodes of a graph using depth first search (dfs) recursive technique

 
Java Code
    import java.util.ArrayList;

    class GraphFindAllPathDFSRecursive{
    
         public static void getAllPaths(int currentNode, int destination, ArrayList<Integer> path,
            ArrayList<ArrayList<Integer>> allPaths, boolean[] visited, int[][] graph) {
           
           // Mark the current node as visited and add it to the path
           visited[currentNode] = true;
           path.add(currentNode);
     
           // Check if we have reached the destination
           if (currentNode == destination) {
               // If destination is reached:
               // Add the copy of the path without reference to the allPaths
               allPaths.add(new ArrayList<>(path));
           } else {
               // If destination is not reached,
               // Traverse to the neighboring unvisited node
               for (int i = 0; i < graph[currentNode].length; i++) {
                   if (graph[currentNode][i] == 1 && i != currentNode && !visited[i]) {
                       getAllPaths(i, destination, path, allPaths, visited, graph);
                   }
               }
           }
     
           // Mark the current node again as unvisited and remove it from the path
           visited[currentNode] = false;
           path.remove(path.size() - 1);
           
       }
     
       public static void main(String[] args) {
           
           // We are given a directed unweighted adjacency matrix of a n nodes graph
           int n = 4;
           int source = 2, destination = 3;
           int[][] graph = {
                   { 1, 1, 1, 1 },
                   { 0, 1, 0, 1 },
                   { 1, 1, 1, 0 },
                   { 0, 0, 0, 1 }
           };
     
           // Creating a ArrayList of ArrayList to store all the paths from source to
           // destination
           ArrayList<ArrayList<Integer>> allPaths = new ArrayList<ArrayList<Integer>>();
     
           // Create a array to store the visited nodes information, the default value of
           // boolean is false
           boolean[] visited = new boolean[n];
     
           // Run the function to get all the possible path from source to destination
           getAllPaths(source, destination, new ArrayList<Integer>(), allPaths, visited, graph);
     
           // Print all the paths
           System.out.println("Possible paths are: ");
           for (ArrayList<Integer> path : allPaths) {
               for (Integer node : path) {
                   System.out.print(node + " ");
               }
               System.out.println();
           }
       }
    
  }
 
Output

Possible paths are: 
2 0 1 3 
2 0 3 
2 1 3 



Thanks for feedback.



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