Java If given a graph adjacency List how do I print all paths start to end

Viewed 53

I am given an adjacency List {A=[B, C, D], B=[A, C, D], C=[A, B], D=[A, B]} with a start and end value and have to print out all possible paths from start to end only once.

So from start C to end D ans is: (C,B,D) (C,A,D) (C,A,B,D) (C,B,A,D)

So far I attempted a DFS solution that I think should work. I would also want to do BFS iteratively but don't know how to translate it. Please give me any advice you have on issues with the code or improvements.

//{A=[B, C, D], B=[A, C, D], C=[A, B], D=[A, B]}
Map<String, Set<String>> adjList= new HashMap<>();
 Stack<String> path  = new Stack<String>();   
 Set<String> onPath  = new HashSet<String>();

    void printRoutes(String start, String des) {
         // add node  to current path from start
         path.push(start);
         onPath.add(start);

         // found path from start to des - currently prints in reverse order because of stack
         if (start.equals(des)) System.out.println(path);
         else {
             for (String w : adjList.get(start)) { //adjList.get is the hashset for start and w will be each letter
                 if (!onPath.contains(w)) printRoutes(w, des);
             }
         }

         // done exploring from start, so remove from path
         path.pop();
         onPath.remove(start);

          };
0 Answers
Related