Codecademy Logo

Graph Traversal

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