Graphs: BFS and DFS

A graph is nodes connected by edges (cities and roads, users and friendships).

🔎 Unravel this example Prerequisites (2)

Learn these first

Queue, Deque and Stack Collections: List, Set, Map

At a glance

Mental model

Exploring a maze of rooms with doors.

What happens, in order

1Adjacency list: Map<Integer, List<Integer>> graph; for each node a list of its neighboursA matrix boolean[n][n] works for small, dense graphs.
2BFS: queue.add(start); visited.add(start); while (!queue.isEmpty()) { u = queue.poll(); for (v : graph.get(u)) if (visited.add(v)) queue.add(v); }It gives the fewest-edges path.
3DFS: the same with a stack, or recursion: visit(u); for (v : graph.get(u)) if (!visited.contains(v)) dfs(v);Used for connectivity, cycle detection and topological order.
4Weighted shortest path: Dijkstra with a PriorityQueue of (distance, node)Dependency ordering: topological sort.

Remember

The visited set is what stops infinite loops in graphs with cycles: mark a node when you add it to the queue, not when you remove it, or it gets queued many times
Complexity of BFS and DFS is O(V + E): every node and edge is looked at once
An adjacency list uses O(V + E) memory, a matrix O(V²)

Watch out

Not tracking visited nodesMarking visited too late in BFSUsing Dijkstra with negative edgesDeep recursion on huge graphs

Example (highlighted lines explain it)

import java.util.*;public class Graphs {  static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {    List<Integer> order = new ArrayList<>();    Set<Integer> visited = new HashSet<>();    Deque<Integer> queue = new ArrayDeque<>();    queue.add(start); visited.add(start);    while (!queue.isEmpty()) {      int u = queue.poll();      order.add(u);      for (int v : graph.getOrDefault(u, List.of())) if (visited.add(v)) queue.add(v);    }    return order;  }  static void dfs(Map<Integer, List<Integer>> graph, int u, Set<Integer> visited) {    if (!visited.add(u)) return;    for (int v : graph.getOrDefault(u, List.of())) dfs(graph, v, visited);  }}

Read the full explanation (about 1 min)

A graph is nodes connected by edges (cities and roads, users and friendships). Store it as an adjacency list (Map<Node, List<Node>>) and explore with breadth-first search (a queue, nearest first) or depth-first search (a stack or recursion, deepest first).

A mental model

Exploring a maze of rooms with doors. BFS checks every room one door away, then two doors away, and so finds the shortest route. DFS follows one corridor to its end before backing up.

How it works

Adjacency list: Map<Integer, List<Integer>> graph; for each node a list of its neighbours. A matrix boolean[n][n] works for small, dense graphs.

BFS: queue.add(start); visited.add(start); while (!queue.isEmpty()) { u = queue.poll(); for (v : graph.get(u)) if (visited.add(v)) queue.add(v); }. It gives the fewest-edges path.

DFS: the same with a stack, or recursion: visit(u); for (v : graph.get(u)) if (!visited.contains(v)) dfs(v);. Used for connectivity, cycle detection and topological order.

Weighted shortest path: Dijkstra with a PriorityQueue of (distance, node). Dependency ordering: topological sort.

Going deeper

The visited set is what stops infinite loops in graphs with cycles: mark a node when you add it to the queue, not when you remove it, or it gets queued many times.

Complexity of BFS and DFS is O(V + E): every node and edge is looked at once. Dijkstra is O((V + E) log V) with a heap and fails with negative weights.

Recursive DFS on a graph with 100,000 nodes in a chain overflows the stack; use an explicit Deque.

Under the hood

An adjacency list uses O(V + E) memory, a matrix O(V²). A Queue makes BFS expand level by level; replacing it with a stack yields DFS, and with a priority queue yields Dijkstra, which is why these algorithms look so alike.

Common mistakes

Not tracking visited nodes.
Marking visited too late in BFS.
Using Dijkstra with negative edges.
Deep recursion on huge graphs.

How Unravel recognises it

When you paste code, Unravel looks for these signs of graphs: bfs and dfs. Spotting them yourself is a good habit when you read unfamiliar code:

Method names you declare: bfs() dfs() dijkstra() topologicalSort() shortestPath()

Part of a learning path

Algorithms and data structures · previous: Trees and tree traversal · next: Backtracking

Related concepts

Queue, Deque and StackJava language PriorityQueue and heapsJava language Trees and tree traversalJava language RecursionJava language

Frequently asked questions

What is Graphs: BFS and DFS?

What are the most common mistakes with Graphs: BFS and DFS?

Not tracking visited nodes. Marking visited too late in BFS. Using Dijkstra with negative edges. Deep recursion on huge graphs.

How can I see Graphs: BFS and DFS in real code?

Paste your own Java into Unravel and it will point out where graphs: bfs and dfs appears, explain how it works at the detail level you choose, and draw the flow of the code around it.