Showing posts with label graph traversal. Show all posts
Showing posts with label graph traversal. Show all posts

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