Graph Traversal

Depth First Search

This is our recursive method for depth-first traversal of a Graph in Java.

public static void depthFirstTraversal(Vertex start, ArrayList<Vertex> visitedVertices) {
  System.out.println(start.getData());

  for (Edge e: start.getEdges()) {
    Vertex neighbor = e.getEnd();
    if (!visitedVertices.contains(neighbor)) {
      visitedVertices.add(neighbor);
      GraphTraverser.depthFirstTraversal(neighbor, visitedVertices);
    }
  }
}

Breadth First Search

This is our recursive method for breadth-first traversal of a Graph in Java.

public static void breadthFirstTraversal(Vertex start) {
  ArrayList<Vertex> visitedVertices = new ArrayList<Vertex>();
  visitedVertices.add(start);

  Queue<Vertex> visitQueue = new LinkedList<>();
  visitQueue.add(start);
  while (!visitQueue.isEmpty()) {
    Object current = visitQueue.remove();
    System.out.println(((Vertex) current).getData());
    for(Edge e : ((Vertex) current).getEdges()) {
      Vertex neighbor = e.getEnd();
      if(!visitedVertices.contains(neighbor)) {
        visitedVertices.add(neighbor);
        visitQueue.add(neighbor);
      }
    }
  }
}