Codecademy Logo

Graph Traversal

Print Cheatsheet

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

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