import java.util.*;

class Graph {

  public static void main(String... args) {
    Graph graph = new Graph();
    graph.addNodes('A', 'B', 'C', 'D' ,'E');
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('B', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'E');
    System.out.println(graph.dfs('A'));
    System.out.println(graph.bfs('A'));
    System.out.println(graph.recursiveDfs('A'));
  }

  private Map<Character, List<Character>> edges = new HashMap<>();

  public void addNodes(Character... nodes) {
    for (Character node : nodes) {
      addNode(node);
    }
  }

  public void addNode(Character node) {
    if (!edges.containsKey(node)) {
      edges.put(node, new LinkedList<>());
    }
  }

  public void addEdge(Character a, Character b) {
    edges.get(a).add(b);
    edges.get(b).add(a);
  }

  public Collection<Character> recursiveDfs(Character start) {
    return accumulateVisited(start, new LinkedHashSet<>());
  }

  private Collection<Character> accumulateVisited(Character start, Collection<Character> seen) {
    Set<Character> visited = new LinkedHashSet<>(seen);
    visited.add(start);
    for (Character v : edges.get(start)) {
      if (!visited.contains(v)) {
        visited.addAll(accumulateVisited(v, visited));
      }
    }
    return visited;
  }

  public Collection<Character> dfs(Character start) {
    Stack<Character> stack = new Stack<>();
    Set<Character> visited = new LinkedHashSet<>();
    stack.push(start);

    while (!stack.isEmpty()) {
      Character v = stack.pop();
      if (!visited.contains(v)) {
        visited.add(v);
        for (Character node : edges.get(v)) {
          stack.push(node);
        }
      }
    }
    return visited;
  }

  public Collection<Character> bfs(Character start) {
    Queue<Character> queue = new LinkedList<>();
    Set<Character> visited = new LinkedHashSet<>();
    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
      Character t = queue.poll();
      for (Character node : edges.get(t)) {
        if (!visited.contains(node)) {
          queue.add(node);
          visited.add(node);
        }
      }
    }
    return visited;
  }
}