Mar 15, 2019

Graph Traversal from given start node to end node

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