BB2.java

importjava.util.*;

publicclassBB2 {
privateMap<Character, Set<Character>> routes;

publicBB2() {
this.routes = newHashMap<>();
 }

publicvoidaddPath(charstart, charend) {
this.routes.putIfAbsent(start, newHashSet<>());
this.routes.putIfAbsent(end, newHashSet<>());

this.routes.get(start).add(end);
this.routes.get(end).add(start);
 }

publicList<String> printAllPathsBetween(charstart, charend) {
List<String> result = newArrayList<>();
List<Character> currPath = newArrayList<>();
Set<Character> visited = newHashSet<>();

currPath.add(start);
visited.add(start);

dfs(routes, visited, result, currPath, start, end);
returnresult;
 }

privatevoiddfs(Map<Character, Set<Character>> routes, Set<Character> visited, List<String> result,
List<Character> currPath, Characterstart, Characterend) {
if (start == end) {
StringBuildersb = newStringBuilder();

for (inti = 0; i < currPath.size(); i++) {
sb.append(currPath.get(i));

if (i != currPath.size() - 1) {
sb.append(" -> ");
 }
 }

result.add(sb.toString());
return;
 }

for (Characterneighbour : routes.get(start)) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
currPath.add(neighbour);

dfs(routes, visited, result, currPath, neighbour, end);

visited.remove(neighbour);
currPath.remove(currPath.size() - 1);
 }
 }
 }

publicstaticvoidmain(String[] args) {
BB2graph = newBB2();

graph.addPath('A', 'B');
graph.addPath('B', 'C');
graph.addPath('B', 'C');
graph.addPath('A', 'C');
graph.addPath('A', 'D');
graph.addPath('D', 'C');
graph.addPath('F', 'E');

List<String> validPathFromAtoC = graph.printAllPathsBetween('A', 'C');
List<String> validPathFromBtoD = graph.printAllPathsBetween('B', 'D');
List<String> invalidPathFromEtoA = graph.printAllPathsBetween('E', 'A');

System.out.println("Valid Path - A to C:");
for (Stringp : validPathFromAtoC) {
System.out.println(p);
 }

System.out.println("\nValid Path - B to D:");
for (Stringp : validPathFromBtoD) {
System.out.println(p);
 }

System.out.println("\nInvalid Path - E to A:");
for (Stringp : invalidPathFromEtoA) {
System.out.println(p);
 }

return;
 }
}