import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;



public class Graph<V> {

    private Map<V, List<V>> graph;

    // create a graph
    public Graph() {
        graph = new HashMap<>();
    }

    // add an edge between nodes
    public void addEdge(V v, V w) {
        // first check if v and w are in graph
        ensureNodeExists(v);
        ensureNodeExists(w);

        // get adjacency list of v
        List<V> adj = graph.get(v);

        // add w to adjacency of v
        adj.add(w);
    }

    public void BFS(V root) {
        // do nothing is root is not in graph
        if (!graph.containsKey(root)) {
            return;
        }

        Set<V> visited = new HashSet<>();

        LinkedList<V> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            V node = queue.poll();

            // add node to visited
            visited.add(node);

            // do something
            System.out.println(" " + node);

            // add all nodes reachable from node to the queue
            Iterator<V> adj = graph.get(node).iterator();
            while (adj.hasNext()) {
                V n = adj.next();
                if (!visited.contains(n)) {
                    queue.add(n);
                }
            }
        }

    }

    public void DFS(V root) {
        // do nothing is root is not in graph
        if (!graph.containsKey(root)) {
            return;
        }

        Set<V> visited = new HashSet<>();
        traverseDFS(root, visited);
    }

    private void traverseDFS(V node, Set<V> visited) {
        // add node to visited
        visited.add(node);

        // do something
        System.out.println(" " + node);

        // recursively traverse the graph
        Iterator<V> adj = graph.get(node).iterator();
        while (adj.hasNext()) {
            V n = adj.next();
            if (!visited.contains(n)) {
                traverseDFS(n, visited);
            }
        }
    }

    private void ensureNodeExists(V v) {
        if (!graph.containsKey(v)) {
            graph.put(v, new ArrayList<>());
        }
    }
}