Skip to main content

​
Graph Traversal Algorithms

Graph traversal algorithms systematically visit all vertices in a graph. Unlike trees, graphs don’t have a root node, so you must specify a starting vertex. The two fundamental traversal algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).

​
Try It Out

Visualize both traversal algorithms in action:

Graph Traversals Visualizer

Watch BFS and DFS algorithms traverse through graphs step-by-step

​
Why Track Visited Vertices?

Unlike tree traversals, graph traversals must track visited vertices to prevent infinite loops. Graphs can have cycles, so without tracking, you could revisit the same vertex endlessly.

​
Breadth-First Search (BFS)

BFS explores all vertices at the current level before moving to the next level. Think of it as exploring outward in waves from the starting vertex.

​
How BFS Works

1

Initialize

Create a queue and a visited list. Add the starting vertex to both.
Queue<Node> queue = new LinkedList<Node>();
List<Node> visited = new LinkedList<Node>();

queue.add(startNode);
visited.add(startNode);
2

Process Queue

While the queue is not empty, remove a vertex and process it.
while (!queue.isEmpty()) {
  Node node = queue.poll();
  System.out.print(node + " ");
}
3

Add Neighbors

For each unvisited neighbor, add it to both the queue and visited list.
for (Node child : node.edges) {
  if (visited.contains(child))
    continue; // Skip if already visited

  queue.add(child);
  visited.add(child);
}
4

Repeat

Continue until the queue is empty, meaning all reachable vertices have been visited.

​
Complete BFS Implementation

public void breadthFirst(String label) {
  Node labelNode = findNode(label);

  if (labelNode == null)
    return;

  // Track visited vertices to prevent infinite loops
  List<Node> visited = new LinkedList<Node>();
  Queue<Node> queue = new LinkedList<Node>();

  queue.add(labelNode);
  visited.add(labelNode);

  while (!queue.isEmpty()) {
    Node node = queue.poll();
    System.out.print(node + " ");

    for (Node child : node.edges) {
      // Critical: Check if we've visited this vertex
      // Without this, we'll loop infinitely!
      if (visited.contains(child))
        continue;

      queue.add(child);
      visited.add(child);
    }
  }
}

​
BFS Example

Consider this directed graph: 
    1
   / \
  2   3
   \ /
    4
Starting from vertex 1:
Traversal Order: [1, 2, 3, 4]
  1. Visit 1 (starting vertex)
  2. Visit 1’s neighbors: 2, 3
  3. Visit 2’s neighbors: 4
  4. 3’s neighbors already visited

​
BFS Complexity

O(V²) with LinkedList, O(V) with HashSet
  • Visit each vertex once: O(V)
  • Check each edge once: O(E)
  • Visited check with LinkedList: O(V) per check
  • Total with LinkedList: O(V²)
  • Total with HashSet: O(V + E) = O(V)
Use a HashSet instead of LinkedList for the visited list to achieve O(1) lookup time and reduce overall complexity to O(V).
O(V)
  • Queue can hold up to O(V) vertices
  • Visited list stores O(V) vertices
  • Total space: O(V)

​
Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. Think of it as diving deep into one path before exploring alternatives.

​
How DFS Works

1

Initialize

Create a stack and a visited list. Add the starting vertex to both.
Stack<Node> stack = new Stack<Node>();
List<Node> visited = new LinkedList<Node>();

stack.add(startNode);
visited.add(startNode);
2

Process Stack

While the stack is not empty, pop a vertex and process it.
while (!stack.isEmpty()) {
  Node node = stack.pop();
  System.out.print(node + " ");
}
3

Add Neighbors

For each unvisited neighbor, push it onto the stack and mark as visited.
for (Node child : node.edges) {
  if (!visited.contains(child)) {
    stack.push(child);
    visited.add(child);
  }
}
4

Repeat

Continue until the stack is empty, meaning all reachable vertices have been explored.

​
Complete DFS Implementation

public void depthFirst(String label) {
  Node labelNode = findNode(label);

  if (labelNode == null)
    return;

  List<Node> visited = new LinkedList<Node>();
  Stack<Node> stack = new Stack<Node>();

  stack.add(labelNode);
  visited.add(labelNode);

  while (!stack.isEmpty()) {
    Node node = stack.pop();
    System.out.print(node + " ");

    for (Node child : node.edges) {
      if (!visited.contains(child)) {
        stack.push(child);
        visited.add(child);
      }
    }
  }
}
DFS can also be implemented recursively, but the stack-based iterative approach is shown here as it’s easier to understand and visualize.

​
DFS Example

Using the same directed graph: 
    1
   / \
  2   3
   \ /
    4
Starting from vertex 1:
Traversal Order: [1, 2, 4, 3]
  1. Visit 1 (starting vertex)
  2. Push 2 and 3, pop 2 (go deep)
  3. Push 4 from 2
  4. Pop 4, then pop 3

​
DFS Complexity

O(V²) with LinkedList, O(V) with HashSet
  • Visit each vertex once: O(V)
  • Check each edge once: O(E)
  • Visited check with LinkedList: O(V) per check
  • Total with LinkedList: O(V²)
  • Total with HashSet: O(V + E) = O(V)
Like BFS, use a HashSet for the visited list to optimize to O(V) time complexity.
O(V)
  • Stack can hold up to O(V) vertices in worst case
  • Visited list stores O(V) vertices
  • Total space: O(V)

​
BFS vs DFS Comparison

AlgorithmData StructureBehavior
BFSQueue (FIFO)Explores level by level
DFSStack (LIFO)Explores depth first

​
Critical Implementation Details

Always track visited vertices! Without tracking, your traversal will enter an infinite loop on graphs with cycles.
Optimization: Replace List<Node> with HashSet<Node> for the visited collection to reduce time complexity from O(V²) to O(V).

​
Common Applications

BFS Applications

  • Shortest path in unweighted graphs
  • Social network friend recommendations (within N degrees)
  • Web crawlers (level by level)
  • Network broadcasting

DFS Applications

  • Cycle detection
  • Topological sorting
  • Solving puzzles with one solution
  • Finding strongly connected components

​
Interactive Learning

The visualizer allows you to:
1

Build a Graph

Create your own graph structure by adding vertices and edges
2

Choose Starting Vertex

Select which vertex to start the traversal from
3

Watch BFS/DFS

See the algorithms traverse through your graph step-by-step
4

Compare Results

Observe how BFS and DFS produce different traversal orders

​
Next Steps

Graph Basics

Review graph structure and operations

Try the Visualizer

Practice BFS and DFS with the interactive tool

​
Key Takeaways

  • BFS uses a queue and explores level by level (breadth-wise)
  • DFS uses a stack and explores depth-first along each branch
  • Always track visited vertices to prevent infinite loops in cyclic graphs
  • Use HashSet for O(1) visited checks instead of LinkedList’s O(V)
  • Both algorithms have O(V) time and space complexity when optimized
  • Choose BFS for shortest paths, DFS for cycle detection and topological sorting

Build docs developers (and LLMs) love

Get started for freeTalk to us