Question

Given an unweighted directed graph G, write a program that counts and prints all simple paths from a given ‘s’ to a given ‘d’. Assume the graph G is represented using adjacent matrix.

Using Java Language

Answer 1

// JAVA program to print all paths from a s to d

import java.util.ArrayList;
import java.util.List;

public class Graph {
   private int v;       // No. of vertices in graph
   private ArrayList<Integer>[] adjList;       // adjacency list
  
   public Graph(int vertices) {
       this.v = vertices;
       initAdjList();
   }

   private void initAdjList() {
       adjList = new ArrayList[v];
      
       for(int i = 0; i < v; i++) {
           adjList[i] = new ArrayList<>();
       }
   }
  
   public void addEdge(int u, int v) {
       adjList[u].add(v);
   }
  
   public void printAllPaths(int s, int d) {
       boolean[] isVisited = new boolean[v];
       ArrayList<Integer> pathList = new ArrayList<>();
       pathList.add(s);
       printAllPathsUtil(s, d, isVisited, pathList);
   }

   private void printAllPathsUtil(Integer u, Integer d, boolean[] isVisited, List<Integer> localPathList) {
       isVisited[u] = true;       // Mark the current node
      
       if (u.equals(d)) {
           System.out.println(localPathList);
           isVisited[u]= false;       // if match found then no need to traverse more till depth
           return ;
       }
      
       // Recur for all the vertices adjacent to current vertex
       for (Integer i : adjList[u]) {
           if (!isVisited[i]) {
               // store current node in path[]
               localPathList.add(i);
               printAllPathsUtil(i, d, isVisited, localPathList);
              
               // remove current node in path[]
               localPathList.remove(i);
           }
       }
         
       isVisited[u] = false;       // Mark the current node
   }

   public static void main(String[] args) {
       Graph g = new Graph(4);
       g.addEdge(0,1);
       g.addEdge(0,2);
       g.addEdge(0,3);
       g.addEdge(2,0);
       g.addEdge(2,1);
       g.addEdge(1,3);
     
       int s = 2;       // arbitrary source
       int d = 3;       // arbitrary destination
      
       System.out.println("Following are all different paths from "+s+" to "+d);
       g.printAllPaths(s, d);
   }
}