Graph Traversal

Imagine a city map with many locations connected by roads:

        A
       / \
      B   C
      |   |
      D---E

If you want to visit every location, you need a systematic way to move through the graph.

This process is called Graph Traversal.

Graph traversal is the process of visiting the vertices of a graph in a systematic way.

The two fundamental graph traversal techniques are:

DFS → Depth-First Search
BFS → Breadth-First Search

Both can visit all reachable vertices, but they explore the graph differently.

Why Do We Need Graph Traversal?

Unlike an array:

10 → 20 → 30 → 40

a graph can have many connections:

There isn't one simple direction in which to move.

Starting from 0, we could explore:

0 → 1 → 3 → 4 → 2

or:

0 → 2 → 4 → 3 → 1

depending on the traversal strategy and neighbor order.

Graph traversal gives us a systematic method for exploring these connections.

The Two Main Traversals

There are two fundamental approaches:

Depth-First Search
        ↓
       DFS

Breadth-First Search
        ↓
       BFS

The easiest way to understand the difference is:

DFS → Go deep first
BFS → Go level by level

DFS — Depth-First Search

Depth-First Search explores as far as possible along one path before backtracking.

Consider:

Starting from 0, one possible DFS order is:

0 → 1 → 3 → 4 → 2

The exact order depends on the order in which neighbors are stored.

The basic idea is:

Start
  ↓
Visit node
  ↓
Go to an unvisited neighbor
  ↓
Keep going deeper
  ↓
Backtrack when necessary

Why Is DFS Called "Depth-First"?

Look at:

Starting from 0, DFS doesn't immediately process 2.

Instead, it goes:

0
↓
1
↓
3

It goes as deep as it can.

When 3 has no unvisited neighbor, it backtracks:

3
↑
1

and then explores 4.

That's why it's called Depth-First Search.

DFS and Recursion

DFS is naturally implemented using recursion.

Why?

Because recursion automatically gives us a stack of function calls.

The basic pattern is:

static void dfs(
    int node,
    ArrayList<ArrayList<Integer>> graph,
    boolean[] visited
) {

    visited[node] = true;

    for (int neighbor : graph.get(node)) {

        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

The most important part is:

visited[node] = true;

We mark the node as visited before exploring its neighbors.

Why Do We Need `visited[]`?

This is one of the biggest differences between tree traversal and graph traversal.

Graphs can contain cycles.

Consider:

A ─ B
|   |
C ─ D

We can travel:

A → B → D → C → A

If we don't remember which nodes we've already visited, the traversal could continue indefinitely.

So we maintain:

boolean[] visited =
    new boolean[vertices];

When we visit a node:

visited[node] = true;

Then we don't visit it again.

Complete DFS Example

Consider:

0 ─ 1
|   |
2 ─ 3

Adjacency list:

0 → [1, 2]
1 → [0, 3]
2 → [0, 3]
3 → [1, 2]

Java:

import java.util.ArrayList;

class Main {

    static void dfs(
        int node,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        visited[node] = true;

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {
                dfs(
                    neighbor,
                    graph,
                    visited
                );
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 4;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(0).add(1);
        graph.get(1).add(0);

        graph.get(0).add(2);
        graph.get(2).add(0);

        graph.get(1).add(3);
        graph.get(3).add(1);

        graph.get(2).add(3);
        graph.get(3).add(2);

        boolean[] visited =
            new boolean[vertices];

        dfs(0, graph, visited);
    }
}

One possible output is:

0 1 3 2

Again, the exact DFS order depends on neighbor ordering.

Iterative DFS Using a Stack

DFS doesn't have to use recursion.

We can explicitly use a Stack.

Remember:

Stack → LIFO
Last In, First Out

Java implementation:

import java.util.Stack;

static void dfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

    boolean[] visited =
        new boolean[graph.size()];

    Stack<Integer> stack =
        new Stack<>();

    stack.push(start);

    while (!stack.isEmpty()) {

        int node = stack.pop();

        if (visited[node]) {
            continue;
        }

        visited[node] = true;

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

So:

DFS
 ↓
Recursion
or
Stack

Both approaches implement the same fundamental depth-first idea.

BFS — Breadth-First Search

Now let's look at the other major traversal.

Breadth-First Search explores the graph level by level.

Consider:

Starting from 0:

Level 0 → 0
Level 1 → 1, 2
Level 2 → 3, 4

So BFS visits:

0 → 1 → 2 → 3 → 4

The exact order can depend on the adjacency-list order.

Why Is BFS Called "Breadth-First"?

DFS goes:

0
↓
1
↓
3

BFS instead processes the entire current level before going deeper:

        0          Level 0
       / \
      1   2        Level 1
     / \
    3   4          Level 2

So:

DFS → Depth first

BFS → Breadth first

Why Does BFS Use a Queue?

BFS naturally uses a Queue.

A queue follows:

FIFO
First In, First Out

Suppose we start at 0.

First:

Queue:
0

Remove 0.

Add its neighbors:

Queue:
1, 2

Remove 1.

Add its unvisited neighbors:

Queue:
2, 3, 4

Then process 2, followed by 3 and 4.

This naturally creates level-by-level traversal.

BFS in Java

import java.util.LinkedList;
import java.util.Queue;

static void bfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

    boolean[] visited =
        new boolean[graph.size()];

    Queue<Integer> queue =
        new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {

        int node = queue.remove();

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                queue.add(neighbor);
            }
        }
    }
}

Notice that we mark the node as visited when we add it to the queue.

This prevents the same node from being added multiple times through different edges.

DFS vs BFS

Let's use:

One possible DFS:

0 → 1 → 3 → 4 → 2

BFS:

0 → 1 → 2 → 3 → 4

The core difference:

DFS	BFS
Goes deep first	Goes level by level
Recursion / Stack	Queue
Uses backtracking	Expands outward
Useful for components/cycles	Useful for shortest paths in unweighted graphs

BFS for Shortest Path

One of the most important properties of BFS is that it can find the shortest path in an unweighted graph, where every edge has equal cost.

Consider:

Suppose we want the shortest path from A to F.

BFS explores:

Distance 0:
A

Distance 1:
B, C

Distance 2:
D, E

Distance 3:
F

So the shortest distance is:

3 edges

One shortest path is:

A → B → D → F

For weighted graphs, ordinary BFS is generally not sufficient; algorithms such as Dijkstra's are used when appropriate.

BFS with Distance

We can maintain a distance array.

static void bfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

    int[] distance =
        new int[graph.size()];

    boolean[] visited =
        new boolean[graph.size()];

    Queue<Integer> queue =
        new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {

        int node = queue.remove();

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                distance[neighbor] =
                    distance[node] + 1;

                queue.add(neighbor);
            }
        }
    }
}

If:

distance[0] = 0

then its neighbors get:

distance = 1

their neighbors get:

distance = 2

and so on.

Finding Connected Components

Suppose the graph is:

0 ─ 1       3 ─ 4
|             \
2              5

There are two separate groups:

Component 1:
0, 1, 2

Component 2:
3, 4, 5

We can use DFS or BFS to count them.

The basic idea is:

For every vertex:
    If it is unvisited:
        Start DFS/BFS
        Increment component count

Java:

static int countComponents(
    ArrayList<ArrayList<Integer>> graph
) {

    int components = 0;

    boolean[] visited =
        new boolean[graph.size()];

    for (int i = 0;
         i < graph.size();
         i++) {

        if (!visited[i]) {

            components++;

            dfs(i, graph, visited);
        }
    }

    return components;
}

This pattern appears frequently in graph problems.

Cycle Detection

Graph traversal is also used to detect cycles.

Consider:

A ─ B
|   |
C ─ D

There is a cycle:

A → B → D → C → A

During traversal, we need to determine whether we've encountered a previously visited vertex in a way that indicates a cycle.

The exact implementation differs between:

Undirected Graph

and:

Directed Graph

For undirected graphs, DFS often tracks the parent of the current node.

For directed graphs, DFS often uses an additional recursion-stack or three-state technique.

DFS for Connected Components

DFS can also be used to explore an entire component.

For:

0 ─ 1
|   |
2 ─ 3

starting from 0:

DFS(0)
 ↓
1
 ↓
3
 ↓
2

Once DFS finishes, every node reachable from 0 has been visited.

This is why DFS is useful for:

Connected components
Cycle detection
Path finding
Topological sorting
Backtracking
Graph exploration

DFS and Backtracking

DFS and backtracking are closely related.

Suppose we're exploring:

A
├── B
│   ├── D
│   └── E
└── C

DFS goes down one branch:

A → B → D

Then when it reaches a dead end, it backtracks:

D → B → E

This same idea appears in:

Maze solving
Permutations
Combinations
Sudoku
N-Queens
Path finding

So when you see a problem involving exploring possibilities and undoing choices, DFS/backtracking is often nearby.

DFS vs BFS in Real Life

Imagine you're looking for a person in a network.

You
├── Friend A
│   ├── Friend D
│   └── Friend E
└── Friend B
    └── Friend F

DFS

You might follow:

You
 ↓
Friend A
 ↓
Friend D

and keep exploring that branch.

BFS

You might first check:

Your direct friends

then:

Friends of friends

then:

Friends of friends of friends

This is why BFS is naturally suited to finding things based on the fewest number of connections.

Graph Traversal with an Adjacency Matrix

Graph traversal can also work with an adjacency matrix.

Suppose:

0 ─ 1
|   |
2 ─ 3

The matrix tells us whether an edge exists.

During DFS, for every vertex we may need to check:

for (int neighbor = 0;
     neighbor < vertices;
     neighbor++) {

    if (graph[node][neighbor] == 1
        && !visited[neighbor]) {

        dfs(
            neighbor,
            graph,
            visited
        );
    }
}

This works, but we scan all possible vertices for each node.

Therefore, with an adjacency matrix:

DFS/BFS → O(V²)

For sparse graphs, adjacency lists are usually more efficient.

Traversal Complexity with Adjacency List

With an adjacency list:

DFS → O(V + E)
BFS → O(V + E)

Why?

We may visit every vertex:

and inspect every edge:

So:

O(V + E)

This is one of the most important formulas in graph DSA.

Traversal Complexity with Adjacency Matrix

With an adjacency matrix:

DFS → O(V²)
BFS → O(V²)

because for each vertex, we may need to scan an entire row of V possible neighbors.

So:

Adjacency List:
O(V + E)

Adjacency Matrix:
O(V²)

A Complete Java Example

Let's implement both DFS and BFS for the same graph.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static void dfs(
        int node,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        visited[node] = true;

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                dfs(
                    neighbor,
                    graph,
                    visited
                );
            }
        }
    }

    static void bfs(
        int start,
        ArrayList<ArrayList<Integer>> graph
    ) {

        boolean[] visited =
            new boolean[graph.size()];

        Queue<Integer> queue =
            new LinkedList<>();

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {

            int node = queue.remove();

            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 5;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);

        System.out.print("DFS: ");

        boolean[] visited =
            new boolean[vertices];

        dfs(0, graph, visited);

        System.out.print("\nBFS: ");

        bfs(0, graph);
    }
}

One possible output is:

DFS: 0 1 3 4 2
BFS: 0 1 2 3 4

The DFS result can change if the order of neighbors in the adjacency lists changes.

When Should You Use DFS?

DFS is a strong choice when the problem involves:

Exploring an entire branch
Connected components
Cycle detection
Topological sorting
Backtracking
Finding paths
Exploring all possible routes
Recursive graph structures

A useful mental clue is:

"Go as deep as possible, then come back."

Think:

DFS
 ↓
Depth
 ↓
Stack / Recursion

When Should You Use BFS?

BFS is particularly useful when the problem involves:

Shortest path in an unweighted graph
Minimum number of steps
Level-by-level exploration
Finding nodes at a certain distance
Multi-source spreading problems

A useful mental clue is:

"Explore everything nearby before going farther."

Think:

BFS
 ↓
Breadth
 ↓
Queue

The Main Idea

Graph traversal means systematically visiting graph vertices.

The two fundamental techniques are:

DFS
Depth-First Search

BFS
Breadth-First Search

DFS

Go deep
   ↓
Backtrack
   ↓
Continue

Usually implemented using:

Recursion / Stack

BFS

Visit current level
       ↓
Visit next level
       ↓
Continue outward

Implemented using:

Queue

The most important complexity to remember is:

Using Adjacency List:

DFS → O(V + E)
BFS → O(V + E)

And because graphs can contain cycles, always remember the importance of:

visited[]

DFS explores deeply through the graph using recursion or a stack, while BFS explores outward level by level using a queue.

Once you understand these two traversals, you're ready for many of the most important graph problems, including connected components, cycle detection, shortest paths, bipartite graphs, topological sorting, and graph-based backtracking.

Why Do We Need Graph Traversal?

The Two Main Traversals

DFS — Depth-First Search

Why Is DFS Called "Depth-First"?

DFS and Recursion

Why Do We Need visited[]?

Complete DFS Example

Iterative DFS Using a Stack

BFS — Breadth-First Search

Why Is BFS Called "Breadth-First"?

Why Does BFS Use a Queue?

BFS in Java

DFS vs BFS

BFS for Shortest Path

BFS with Distance

Finding Connected Components

Cycle Detection

DFS for Connected Components

DFS and Backtracking

DFS vs BFS in Real Life

DFS

BFS

Graph Traversal with an Adjacency Matrix

Traversal Complexity with Adjacency List

Traversal Complexity with Adjacency Matrix

A Complete Java Example

When Should You Use DFS?

When Should You Use BFS?

The Main Idea

DFS

BFS

Why Do We Need `visited[]`?