Simple Graph Search Example

README.md

Graph Search

A quick graph search example that I threw together. The Graph class has a breadth first search, depth first search, and a recursive depth first search. This example simply visits all of the nodes in the graph. It could be extended to do more useful operations, such as find a path from one node to another.

Build

You will need Java 1.7 or greater to run this example, as I make use of the diamond notation. Download Graph.java and run the following:

> javac Graph.java
> java Graph

Graph.java

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