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);
};