A graph represents connections between vertices. A vertex might be a room, account or station; an edge represents a relationship or route. Unlike a tree, a graph may contain cycles, several routes to the same destination, and disconnected groups.
Breadth-first search, or BFS, explores nearby vertices before more distant ones. Depth-first search, or DFS, follows a route as far as possible before exploring alternatives. Both need a record of visited vertices so a cycle cannot keep the traversal running forever.
Directed, undirected and weighted graphs
In a directed graph, an edge from A to B does not imply an edge from B to A. A one-way service dependency is a directed relationship. In an undirected graph, each connection works both ways, so an adjacency-list representation normally stores each endpoint in the other's neighbor list.
A weighted edge also stores a cost, such as travel time. The examples here are unweighted: each edge counts as one step. This distinction matters because BFS finds a route with the fewest edges, not necessarily the lowest cost when edges have different weights.
A graph can contain isolated vertices. Represent these with empty neighbor lists instead of omitting them when your algorithm needs to know the complete vertex set. Decide whether duplicate edges and self-loops are valid for your problem; neither should cause infinite traversal when visited handling is correct.
The terms vertex and node are often used interchangeably. What changes from a tree is the relationship model: there is no required single parent, root, or left-versus-right ordering.
Adjacency lists versus matrices
An adjacency list stores each vertex's outgoing neighbors. It takes O(V+E) space for V vertices and E stored edges. This representation is convenient for sparse graphs because it avoids allocating entries for every nonexistent connection.
An adjacency matrix uses a two-dimensional array indexed by vertex positions. It takes O(V²) space but can answer whether a particular edge exists with one array lookup. Iterating all neighbors of a vertex generally scans an entire row.
For an undirected adjacency list, the same logical connection is stored twice. Complexity notation still uses O(V+E), because doubling the edge storage changes a constant rather than its growth rate. When counting edges in output or statistics, account for that duplication explicitly.
Shortest paths in an unweighted graph
BFS reaches a vertex first using the fewest edges from the start. Record distance[next] = distance[current] + 1 on first discovery. Record a predecessor at the same time if you want to reconstruct the route, rather than only report its length.
To reconstruct, start at the destination and follow predecessor links back to the start, then reverse that sequence. A missing destination in the distance map means it was not reachable; it should not silently receive a zero distance.
BFS stops after the reachable portion of a graph. For an undirected graph, find all connected components by starting another traversal from each vertex that remains unvisited. Strongly connected components in a directed graph require a different algorithm; repeated ordinary BFS alone does not identify them. A route from one start cannot discover a disconnected island.
For unequal nonnegative edge weights, study Dijkstra's algorithm and a priority queue. Replacing BFS's ordinary queue with a priority queue without also maintaining and updating distances is not a correct shortest-path implementation.
Complexity and safe traversal boundaries
With adjacency lists and expected constant-time set operations, BFS and DFS take O(V+E) time over the reachable portion. Each vertex is discovered once and its outgoing edges are examined once. Both need O(V) auxiliary storage in the worst case.
Recursive DFS can overflow the Java stack on a long chain. An explicit stack based on ArrayDeque avoids relying on call-stack depth. To preserve the displayed order when pushing several neighbors, push them in reverse order, because a stack removes the last pushed entry first.
Do not modify neighbor lists while iterating over them unless the surrounding design deliberately supports it. Validate that a supplied start exists if unknown vertex names should be rejected; our getOrDefault convenience otherwise treats a missing vertex as having no outgoing edges.
Graph Traversal Summary
- Define direction and weights before choosing an algorithm.
- Use a queue for BFS and recursion or a stack for DFS.
- Mark first discovery to handle cycles and repeated incoming edges.
- Track predecessors when an actual path is needed.
- Practice branching searches in backtracking.
Graph Traversal Examples
Each example shows the code, the output it produces and what each part does.
Representing a graph with adjacency lists
This directed map describes rooms reachable through one-way doors.
Map.of and List.of create unmodifiable containers here. Use mutable collections when the application needs to add connections later. The neighbor lists determine our traversal order; the map's own iteration order does not determine which neighbor BFS visits first.
import java.util.List;
import java.util.Map;
public class RoomGraphExample {
public static void main(String[] args) {
Map<String, List<String>> graph = Map.of(
"Entry", List.of("Hall", "Studio"),
"Hall", List.of("Exit"),
"Studio", List.of("Hall"),
"Exit", List.of());
System.out.println(graph.get("Entry"));
System.out.println(graph.get("Exit").size());
}
}[Hall, Studio]
0Line-by-line explanation
- Lines 6 to 10Every room has a key, including Exit, which has no outgoing neighbors.
- Line 7Entry has two outgoing edges in a deliberate neighbor order.
- Lines 11 to 12Looking up a vertex retrieves its neighbors rather than searching a matrix.
Breadth-first search with a queue
Save this runnable program as RoomBreadthExample.java.
After Entry, the queue holds Hall and Studio. Processing Hall appends Exit behind Studio. Processing Studio sees Hall already visited and adds nothing. Marking on enqueue prevents several incoming edges from creating repeated pending copies.
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class RoomBreadthExample {
static void bfs(Map<String, List<String>> graph, String start) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new ArrayDeque<>();
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
String room = queue.poll();
System.out.println(room);
for (String next : graph.getOrDefault(room, List.of())) {
if (visited.add(next)) queue.offer(next);
}
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = Map.of(
"Entry", List.of("Hall", "Studio"),
"Hall", List.of("Exit"),
"Studio", List.of("Hall"),
"Exit", List.of("Entry"));
bfs(graph, "Entry");
}
}Entry
Hall
Studio
ExitLine-by-line explanation
- Lines 10 to 13The start is marked visited before being queued.
- Lines 14 to 16FIFO removal processes vertices in discovery layers.
- Lines 17 to 18Set.add returns true only on first discovery, so a room enters the queue once.
- Line 28Exit leads back to Entry, creating a cycle that the visited set safely stops.
Depth-first search with recursion
DFS uses the call stack to remember where to return after exploring a branch.
Hall's branch reaches Exit before the call returns to Entry and chooses Studio. That order differs from BFS even though both discover the same reachable rooms.
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class RoomDepthExample {
static void dfs(Map<String, List<String>> graph,
String room, Set<String> visited) {
if (!visited.add(room)) return;
System.out.println(room);
for (String next : graph.getOrDefault(room, List.of())) {
dfs(graph, next, visited);
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = Map.of(
"Entry", List.of("Hall", "Studio"),
"Hall", List.of("Exit"),
"Studio", List.of("Hall"),
"Exit", List.of("Entry"));
dfs(graph, "Entry", new HashSet<>());
}
}Entry
Hall
Exit
StudioLine-by-line explanation
- Line 9Returning on an already visited room prevents cycle recursion.
- Lines 10 to 12The current room is printed before recursively exploring its neighbors.
- Lines 18 to 21The same graph and neighbor order are used as in BFS.
- Line 22One shared visited set follows every recursive branch.
Graph Traversal FAQ
Does DFS always find the shortest route?
No. Its first route depends on neighbor order and may be longer than another available route.
Can I use a graph to represent a tree?
Yes. A tree is a special graph, but a general graph traversal still needs visited handling unless its tree assumptions are explicitly enforced.
When should I use BFS instead of DFS?
Use breadth-first search when you need the fewest edges from a start vertex, such as the shortest route in an unweighted map or degrees of separation in a social network. Use depth-first search for reachability, detecting cycles, topological ordering and exploring every path.
How do I find shortest paths when edges have weights?
BFS ignores weights, so use Dijkstra's algorithm for non-negative weights: a PriorityQueue always expands the vertex with the smallest known distance. Graphs with negative edge weights need Bellman-Ford instead.
Why can recursive DFS fail on large graphs?
Each recursive call uses stack space, so a long path through tens of thousands of vertices can cause a StackOverflowError. An iterative DFS with an ArrayDeque as an explicit stack has no such limit, apart from the heap memory available.
Graph Traversal Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
An undirected connection joins Library and Cafe. What should its adjacency lists contain?
Entry lists Hall before Studio; Hall leads to Exit. Which order does BFS print?
Graph Traversal Quiz
2 questions to check what you learned.
Why mark a BFS vertex visited when it enters the queue?
- To prevent another edge from enqueuing it again
- To sort its neighbors alphabetically
- To remove every cycle from the graph permanently
When does ordinary BFS guarantee a lowest-cost path?
- When every traversed edge has the same cost
- For every graph with positive but unequal weights
- Whenever the graph contains no self-loops