package algo;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public class GraphTraversal {
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
List<String> aList = new ArrayList<String>();
aList.add("F");
aList.add("B");
aList.add("C");
graph.put("A", aList);
List<String> bList = new ArrayList<String>();
bList.add("E");
bList.add("A");
bList.add("D");
graph.put("B", bList);
List<String> dList = new ArrayList<String>();
dList.add("E");
dList.add("A");
dList.add("Z");
graph.put("D", dList);
buildPath(graph, "A", "Z");
}
public static void buildPath(Map<String, List<String>> graph, String start, String end){
Set<String> processedNode = new HashSet<>();
Stack<String> stack = new Stack<>();
processedNode.add(start);
stack.push(start);
processPath(graph, processedNode, stack, start, end);
}
public static void processPath(Map<String, List<String>> graph, Set<String> processedNode, Stack<String> stack, String start, String end){
if(start.equals(end)){
System.out.println(stack);
return;
}
List<String> children = graph.get(start);
if(children != null) {
for(String child : children){
if(!processedNode.contains(child)){
stack.push(child);
processPath(graph, processedNode, stack, child, end);
}
}
}
stack.pop();
}
}