Algorithms · Lecture Notes
Chapter 5: Graph Traversal
Roads between cities, friendships in a social network, routers on the internet, and dependencies among the modules of a compiler are all described by the same structure: objects and the connections between them. That structure is a graph. The first step in asking questions about a graph is to walk through it in an orderly way. These notes begin with a short review of graph terminology and of how a graph is stored in memory. They then treat the two basic traversals in detail: depth-first search (DFS) and breadth-first search (BFS). The final sections build on these two: shortest paths in unweighted graphs, maze solving, strongly connected components by the algorithms of Tarjan and Kosaraju, topological sorting, and the bipartiteness test. Every algorithm comes with code, a step-by-step trace, and a cost analysis.
Learning outcomes
- Graph concepts
- Tell directed, undirected, weighted, bipartite, and complete graphs, trees, and non-simple graphs apart; represent a graph by an adjacency list and an adjacency matrix and compare the memory and time costs of the two.
- DFS
- Write depth-first search both recursively and with an explicit stack; trace the visit order step by step; explain backtracking and why the two versions give different orders.
- BFS
- Write breadth-first search with a queue; use the notions of layer, parent, and unweighted shortest path; find a shortest path in a maze.
- Tarjan and applications
- Find strongly connected components with index and low-link values; compare the result with Kosaraju's algorithm; apply topological sorting and the bipartiteness test; justify the O(V + E) running time of all the traversal algorithms.
5.1Graphs and their representations
Much of the world is organized like a network. Cities are joined by roads, people by acquaintance, computers by cables. What these networks share is a handful of objects and connections between some pairs of them. It does not matter what the objects are, or whether a connection is physical or logical. Mathematics calls this common structure a graph. Graph algorithms answer the questions we ask about such networks. Is there a road between two cities? Which road is shortest? Into which groups does the network fall apart? If one cable is cut, is the network split in two?
5.1.1What is a graph?
A graph G = (V, E) consists of two sets. V is the set of vertices (also called nodes), and E is the set of edges; each edge joins two vertices. The two vertices an edge joins are its endpoints, and two vertices joined by an edge are adjacent.
The cost of a graph algorithm depends on two sizes of the graph. In these notes the letter V stands both for the vertex set and for the number of vertices, and E both for the edge set and for the number of edges; the context makes clear which is meant. Running times are written in terms of both numbers, as in O(V + E) or O(V2). We use two numbers instead of a single n because graphs with the same number of vertices can have very different numbers of edges. A graph on ten vertices may have no edges at all, or as many as forty-five.
Figure 5.1 shows a small road network. To get from Ordu to Erzurum one can take Ordu–Giresun–Trabzon–Erzurum, Ordu–Samsun–Sivas–Erzurum, and so on. A sequence of vertices obtained by starting at a vertex and moving at each step along an edge to a neighbor is called a path. The length of a path is the number of edges it contains; the path Ordu–Giresun–Trabzon–Erzurum has length 3. A path that returns to its starting vertex without repeating an edge is a cycle. In the figure, Ordu–Giresun–Sivas–Samsun–Ordu is a cycle.
The number of edges at a vertex is its degree. In the figure Giresun has degree 3 (Ordu, Trabzon, Sivas) and Samsun has degree 2. The degrees always sum to twice the number of edges, because each edge contributes one to the degree of each of its two endpoints. Here the degrees are 2, 3, 2, 2, 3, 2, which add up to 14 = 2 · 7. This simple observation is used directly in the cost analysis of the traversals: in an undirected graph the adjacency lists have total length 2E.
A graph in which there is a path between any two vertices is connected. The network in the figure is connected: one can travel from every city to every city. A graph that is not connected falls apart into pieces that are connected inside and have no edge between them. Each such piece is a connected component.
5.1.2Kinds of graphs
Edges may have a direction, a weight, or some special arrangement, and these properties decide which algorithm to use. Figure 5.2 shows the eight most common kinds with small examples.
- Directed graph. Every edge has a start and an end, and can be traversed only in the direction of the arrow. The edge u → v lets us go from u to v but not back. One-way streets, links from one web page to another, and dependencies of the form "task A must finish before task B" are directed graphs. In a directed graph the number of edges entering a vertex is its in-degree, and the number leaving it is its out-degree.
- Undirected graph. Edges can be traversed in both directions. Friendship is symmetric, so a social network is modeled by an undirected graph. An undirected edge can be thought of as two directed edges, and it is usually stored that way in memory.
- Weighted graph. Every edge carries a number. The number may be a distance, a time, a cost, or a capacity. In a road network the weights are kilometers; in a computer network, latencies. In a weighted graph the length of a path is measured not by the number of edges but by the sum of the weights.
- Bipartite graph. The vertices can be split into two sets so that every edge joins vertices in different sets; no edge joins two vertices of the same set. Matchings between students and courses, or between workers and jobs, have this structure.
- Cyclic graph. It contains at least one cycle. In the example in the figure, A–D–C–B–A is a path that returns to where it started. A graph with no cycle is acyclic. Directed acyclic graphs (DAGs) have a special place in task scheduling.
- Tree. A connected, acyclic, undirected graph. In a tree there is exactly one path between any two vertices, and a tree with V vertices always has V − 1 edges. Binary search trees, heaps, and file-system directories are familiar examples.
- Complete graph. Every pair of vertices is joined by an edge. A complete graph on n vertices has n(n − 1)/2 edges. Each vertex is joined to the other n − 1 vertices; every edge is counted twice this way, so the total is halved. On four vertices this gives 4 · 3/2 = 6 edges, on ten vertices 10 · 9/2 = 45. A simple undirected graph cannot have more edges than this.
- Non-simple graph. It contains several edges between the same two vertices (multiple edges) or an edge joining a vertex to itself (a self-loop). A graph with neither is a simple graph. Unless stated otherwise, the graphs in these notes are simple; the only exception is the self-loop in the strongly connected components example.
These kinds are not mutually exclusive. A road map can be directed (one-way streets), weighted (lengths), and cyclic all at once. A tree is always bipartite: put the vertices at even distance from the root in one set and those at odd distance in the other, and every edge joins different sets. This observation is also the basis of the bipartiteness test.
5.1.3Families of graph algorithms
Algorithms on graphs fall into four large groups according to the question they answer:
- Traversal. Starting from one vertex, visit all reachable vertices in an orderly sequence. Depth-first search follows one branch to its end; breadth-first search sweeps the network layer by layer. This group is the subject of these notes.
- Shortest paths. Find the shortest paths from one start vertex to the others. In a weighted graph Dijkstra's algorithm does this.
- Minimum spanning tree (MST). Choose the edges that connect all vertices at the least total cost. Kruskal's algorithm is a well-known example.
- Network flow. In a network whose edges have capacities, find the largest amount of flow that can be sent from a source to a sink.
Traversal is the most basic of these groups, because most of the other algorithms contain a traversal inside. Dijkstra's algorithm resembles a breadth-first search whose queue is replaced by a priority queue. Flow algorithms look for an augmenting path in every round by a traversal. Table 5.1 gives an everyday counterpart for three of the algorithms.
| Algorithm | Everyday example |
|---|---|
| DFS | Searching a maze: follow one corridor to its end, then turn back |
| BFS | A piece of news spreading through a city from person to person: first the immediate circle, then their circles |
| Dijkstra | A courier finding the route that completes the deliveries in the shortest time |
5.1.4Storing a graph in memory
The first decision for a program that works with a graph is how to store it, and this decision directly affects the speed of the algorithm. There are two common representations: the adjacency list and the adjacency matrix. In both, the vertices are numbered 0, 1, …, V − 1, so a vertex can serve as an array index.
Adjacency list. For each vertex, a list of its neighbors. The V lists are kept in an array; adj[u] holds the neighbors of u.
Adjacency matrix. A table of size V × V. If there is an edge between u and v, then M[u][v] = 1; otherwise M[u][v] = 0. In a weighted graph the weight of the edge is stored instead of 1.
The adjacency list of the graph in Figure 5.3 is:
0: 1, 2
1: 0, 2
2: 0, 1, 3
3: 2In an undirected graph every edge appears in two lists. The edge 0–1 is written as 1 in the list of 0 and as 0 in the list of 1. The total length of the lists is therefore 2E = 8. In a directed graph the edge u → v is added only to the list of u, and the total length is E. The adjacency matrix of the same graph is given in Table 5.2.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
The matrix of an undirected graph is symmetric about the diagonal: M[u][v] = M[v][u]. In a simple graph there are no self-loops, so the diagonal is zero. The number of 1s in a row equals the degree of that vertex; row 2 has three 1s, and vertex 2 has degree 3.
In Java the adjacency list is built as an array of lists. The fragment below builds the lists of an undirected graph from an array edges that gives the edges as pairs {u, v}:
List<Integer>[] adj = new List[n];
for (int v = 0; v < n; v++)
adj[v] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]); /* undirected: add reverse too */
}The first loop creates an empty list for every vertex: O(V). The second loop makes two insertions per edge: O(E). Construction takes O(V + E) time. If the edges are given in the order (0, 1), (0, 2), (1, 2), (2, 3), the result is exactly the lists above. For a directed graph the second add line is left out. All Java code in these notes uses an array List<Integer>[] adj of this form.
The costs of the two representations are compared in Table 5.3.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Memory | O(V + E) | O(V2) |
| All neighbors of u | O(deg(u)) | O(V) |
| Is (u, v) an edge? | O(deg(u)) | O(1) |
| Traversal (DFS or BFS) | O(V + E) | O(V2) |
Each row of the table has a reason. The list stores one list head per vertex and one or two items per edge, so its memory is proportional to V + E. The matrix allocates V2 cells regardless of the number of edges. Visiting the neighbors of a vertex means reading only that vertex's list in the list representation. In the matrix one has to look at all V cells of the row, because it is not known in advance which cells hold a 1. Asking whether a particular edge exists is a single cell read in the matrix; in the list, the list of u must be scanned from the beginning.
Compare the approximate work of BFS under the two representations on an undirected graph with V = 1000 vertices and E = 3000 edges.
- Adjacency list. BFS takes each vertex off the queue once and reads each vertex's list once. The lists have total length 2E = 6000. The work is about V + 2E = 1000 + 6000 = 7000 basic steps.
- Adjacency matrix. For each vertex one row of the matrix is scanned from start to end. The work is V · V = 1,000,000 cell reads.
- Ratio. 1,000,000 / 7000 ≈ 143. On this graph the matrix does about 140 times as much work. Most cells are 0, and reading these zeros is wasted effort.
A graph whose number of edges is far below the maximum possible value V(V − 1)/2 is called sparse; one close to it is dense. Most real networks are sparse. In a road network the number of roads meeting at an intersection is limited to a few; a network with a million intersections may have about three million roads. The adjacency list stores this network in a few million items. The matrix would need 1012 cells, which is 125 gigabytes even at one bit per cell. This is why the adjacency list is the default representation for traversal algorithms. The matrix is preferred when the graph is small and dense, or when the question "are these two vertices adjacent?" is asked very often.
Adding an undirected edge to only one list. If the edge 0–1 is written only to adj[0], the graph silently becomes a directed graph with the edge 0 → 1. A traversal starting at 1 can no longer reach 0, and the number of connected components comes out wrong. In an undirected graph the lists must have total length 2E; this is an easy check on the construction.
5.2Graph traversal
5.2.1The traversal problem
Graph traversal means visiting every vertex reachable from a start vertex in an orderly sequence, exactly once. A visit includes the work done at the vertex: printing it, incrementing a counter, writing its distance into an array.
The purpose of a traversal is to explore the structure of the graph systematically. Questions such as which vertices are reachable, how many components there are, and whether the graph has a cycle can be answered by a traversal. The "exactly once" condition says two things. First, no reachable vertex may be skipped. Second, no vertex may be processed twice.
The second condition holds automatically in trees. When a tree is traversed from the root, each vertex is reached by a single path, because a tree has no cycles. In a general graph a vertex can be reached by many paths, and cycles may exist. In the graph of Figure 5.3 we go from 0 to 1, from 1 to 2, and from 2 back to 0. Unless the algorithm remembers which vertices it has already seen, it will circle forever around the cycle 0–1–2. For this reason every traversal keeps a visited array: visited[v] is a boolean array that tells whether v has already been marked. We move to a vertex only if it is not marked.
A traversal sees only the vertices reachable from the start. In a directed graph with no path from 0 to 5, a traversal from 0 never visits 5. To traverse all vertices of a graph that is not connected, the traversal is restarted from every vertex that has not been visited yet. In an undirected graph each restart discovers a new connected component.
5.2.2Two approaches: stack and queue
At every moment during a traversal the algorithm holds a "waiting list" of vertices that have been discovered but not yet processed. The next vertex is chosen from this list, and how it is chosen determines the character of the traversal. The only difference between the two basic approaches is the data structure that holds the waiting list.
- Depth-first search (DFS) keeps the waiting list in a stack. A stack works by the last in, first out (LIFO) rule. The most recently discovered vertex is processed first, so the algorithm goes from a vertex to its neighbor, then to that neighbor's neighbor, as deep as it can. When there is nowhere left to go, it returns to the previous vertex. This return is called backtracking.
- Breadth-first search (BFS) keeps the waiting list in a queue. A queue works by the first in, first out (FIFO) rule. The vertex discovered first is processed first, so the algorithm visits first the vertices one edge away from the start, then those two edges away. The traversal proceeds level by level.
The stack and the queue are two basic data structures; in both, insertion and removal take O(1) time. In Java, push and pop of ArrayDeque serve as a stack, and add and poll of the Queue interface serve as a queue. In a recursive DFS the stack is not visible. The call stack takes its place: each recursive call pushes a frame and each return pops one.
5.3Depth-first search (DFS)
Depth-first search is perhaps the most widely used building block of graph algorithms. Cycle detection, topological sorting, strongly connected components, and bridge finding are all obtained by adding a few lines to a DFS. This section presents DFS first through an analogy, then on a tree, and then with two Java versions, recursive and stack-based.
5.3.1The idea: go deep first
DFS behaves like a traveler in a maze. The traveler enters a corridor and goes on until a dead end. At the dead end, they return to the last junction they passed and turn into a corridor they have not tried. When that one ends, they go back to the junction before. This continues until every corridor of the maze has been tried. Two things make the traveler's job easier: they mark the places they have passed with chalk, so as never to walk the same corridor twice, and they remember the junctions to return to, in order.
Depth-first search (DFS), after visiting a vertex, moves to its first unvisited neighbor and continues the same way from there. When a vertex has no unvisited neighbor left, DFS returns to the vertex from which it came and tries the next neighbor there.
The chalk marks in the analogy are the array visited[]. The junctions to return to are remembered by a stack. In the recursive version this stack is the program's call stack: when the work on a vertex is finished, its call returns and control passes to the previous vertex automatically. The iterative version uses an explicit Deque object.
During DFS a vertex is in one of three states. The states are shown by colors, and the figures in these notes use the same colors:
- White: the vertex has not been discovered yet.
- Yellow: the vertex has been discovered but its work is still going on. Its call sits on the stack; some of its neighbors have not been examined yet.
- Dark: the work on the vertex is finished; all its neighbors have been examined and its call has returned.
The edges used to reach a vertex for the first time form a tree, called the DFS tree. Its root is the start vertex, and the parent of each vertex is the vertex that discovered it. In Figure 5.5 the edges a–b, b–d, and b–e belong to the DFS tree. The other edges of the graph do not enter the tree, but they are still examined and carry important information. For example, an edge to a yellow vertex signals a cycle.
The visit order of DFS depends on the order in which neighbors are tried. If the neighbor lists of the same graph are ordered differently, a different but equally valid DFS order results. Unless stated otherwise, these notes try neighbors in the order of the adjacency list. In undirected examples the lists are in increasing or alphabetical order.
5.3.2Visit order on a tree
The clearest example of DFS's "go deep, then come back" pattern is a tree, because a tree has no cycles and no vertex can be reached in two ways. Figure 5.6 shows three moments of a DFS that starts at the root of a tree with ten vertices. The numbers above the vertices give the order in which DFS visits them.
The edges of the tree are 1–2, 1–5, 1–9, 2–3, 3–4, 5–6, 5–8, 6–7, and 9–10. Children are tried from left to right.
- The root 1 is visited. Stack: 1.
- The first undiscovered neighbor of 1 is 2; DFS descends to 2. Stack: 1 → 2.
- From 2 to 3, from 3 to 4. Stack: 1 → 2 → 3 → 4. The end of the leftmost branch has been reached.
- Vertex 4 has no undiscovered neighbor; 4 finishes and DFS returns to 3. Neither 3 nor 2 has another undiscovered neighbor, so both finish. This chain of returns continues up to 1. Stack: 1.
- The next child of 1, namely 5, is visited. From 5 to 6, from 6 to 7. Stack: 1 → 5 → 6 → 7.
- 7 and 6 finish; DFS returns to 5. The next child of 5, namely 8, is visited. Stack: 1 → 5 → 8.
- 8 and 5 finish; DFS returns to 1. The last child of 1, namely 9, is visited, then the child 10 of 9. Stack: 1 → 9 → 10.
- 10, 9, and 1 finish; the stack empties.
The visit order is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Because the vertices in this example are already numbered in DFS order, the order is simply the increasing order of the numbers. On the same tree BFS would give 1, 2, 5, 9, 3, 6, 8, 10, 4, 7, with all children of the root coming first.
The example shows that the stack holds at most four vertices. This number is the count of vertices on the path from the root to the deepest leaf. The DFS stack never goes deeper than the longest path, because at every moment it holds the tree path from the root to the current vertex.
5.3.3Recursive pseudocode
The definition of DFS uses DFS itself: to run DFS from a vertex means to mark it and run DFS from each of its undiscovered neighbors. The algorithm is therefore most naturally written recursively. Two forms are common in the literature. The first is the one often seen in English-language sources:
procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w
that are in G.adjacentEdges(v) do
if vertex w is not labeled
as discovered then
call DFS(G, w)The second moves the check to the beginning of the call:
DFS(v, visited):
if v is not in visited:
add v to visited
process v (for example, print it)
for each neighbor w of v:
DFS(w, visited)The two versions produce the same visit order. The difference is where the "already visited?" check is made. The first version checks a neighbor before calling; for a marked neighbor no call is made at all. The second version calls for every neighbor and checks at the start of the call; a call opened for a marked vertex returns immediately. The second version looks shorter but makes needless calls. A call is opened for every edge, so the number of calls is O(E). The order of growth does not change, but the constant factor grows. The Java code follows the first version.
The pseudocode visits only the vertices reachable from a single start vertex. To traverse all vertices of a graph that is not connected, DFS is restarted from every unvisited vertex. In an undirected graph each start traverses one connected component completely.
5.3.4Code: dfs()
void dfs(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int w : adj[v])
if (!visited[w])
dfs(w, visited);
}The code is the Java counterpart of the first pseudocode and works as follows, line by line:
visited[v] = true;marks the vertex. The mark is set as soon as the vertex is visited. This way v is not called a second time even if one of its neighbors has an edge leading back to v.System.out.print(v + " ");does the work at the vertex; here the work is printing it. Because this line is at the start of the call, vertices are printed in discovery order. Had the line been placed after the loop, vertices would be printed in finishing order; topological sorting uses this second order.for (int w : adj[v])walks through the adjacency list of v from beginning to end.if (!visited[w]) dfs(w, visited);descends into an undiscovered neighbor. When the recursive call returns, every vertex reachable from w has been visited and the loop continues with the next neighbor. Backtracking is exactly this return of the call.
The method takes the visited array as a parameter. The array is created once and all calls share it. This makes it easy to restart DFS on a graph that is not connected: the same array carries the marks of the first start over to the second.
5.3.5Code trace: dfs(0)
The graph used in the trace is directed. Its edges are 0→1, 0→2, 0→7, 1→2, 2→0, 2→3, 2→4, 3→5, 4→6, and 5→6. The adjacency lists are filled in this order: adj[0] = [1, 2, 7], adj[2] = [0, 3, 4]. Vertices 6 and 7 have no outgoing edges. The graph has the cycles 0 → 1 → 2 → 0 and 0 → 2 → 0; without a visited array DFS would circle in them forever.
dfs(0) has been called, and 0 has been marked and printed. The double-headed line between 0 and 2 stands for two separate edges: 0→2 and 2→0.| Step | Event | Call stack | Output |
|---|---|---|---|
| 1 | dfs(0): 0 is marked and printed | 0 | 0 |
| 2 | neighbor 1 of 0 is unmarked → dfs(1) | 0, 1 | 0 1 |
| 3 | neighbor 2 of 1 is unmarked → dfs(2) | 0, 1, 2 | 0 1 2 |
| 4 | neighbor 0 of 2 is marked → skipped | 0, 1, 2 | 0 1 2 |
| 5 | neighbor 3 of 2 is unmarked → dfs(3) | 0, 1, 2, 3 | 0 1 2 3 |
| 6 | neighbor 5 of 3 is unmarked → dfs(5) | 0, 1, 2, 3, 5 | 0 1 2 3 5 |
| 7 | neighbor 6 of 5 is unmarked → dfs(6) | 0, 1, 2, 3, 5, 6 | 0 1 2 3 5 6 |
| 8 | 6, 5, and 3 finish; control returns to 2 | 0, 1, 2 | 0 1 2 3 5 6 |
| 9 | neighbor 4 of 2 is unmarked → dfs(4) | 0, 1, 2, 4 | 0 1 2 3 5 6 4 |
| 10 | neighbor 6 of 4 is marked → skipped | 0, 1, 2, 4 | 0 1 2 3 5 6 4 |
| 11 | 4, 2, and 1 finish; control returns to 0 | 0 | 0 1 2 3 5 6 4 |
| 12 | neighbor 2 of 0 is marked → skipped | 0 | 0 1 2 3 5 6 4 |
| 13 | neighbor 7 of 0 is unmarked → dfs(7) | 0, 7 | 0 1 2 3 5 6 4 7 |
| 14 | 7 and 0 finish; dfs(0) returns | empty | 0 1 2 3 5 6 4 7 |
Three moments of the trace deserve attention. In step 4 the edge from 2 to 0 is examined. Vertex 0 is marked and is still on the call stack, that is, yellow. This edge is proof of a cycle: the stack holds a tree path from 0 to 2 (0 → 1 → 2), and the edge 2 → 0 closes it. The code merely skips it here; a version that detects cycles can report "cycle found" at this point.
In step 8 three calls return one after another. Vertex 6 has no outgoing edges at all; the only neighbor of 5 is 6, and the only neighbor of 3 is 5. Control returns to the for loop in 2 at the place where it left off, and the next neighbor, 4, is tried. This is what backtracking looks like in code: there is no separate "go back" command; it is enough for the calls to return.
In step 10 the edge from 4 to 6 is examined. Vertex 6 is marked but is not on the stack; its work finished long ago. This edge does not form a cycle: there is no path back from 6 to 4. In a directed graph only an edge to a vertex that is on the stack signals a cycle; an edge to a finished vertex does not.
The output is 0 1 2 3 5 6 4 7. The call stack reached at most six frames (step 7: 0, 1, 2, 3, 5, 6). In the DFS tree the path from 0 to 6 is 0 → 1 → 2 → 3 → 5 → 6, five edges long. Yet the graph has a path from 0 to 6 of only three edges: 0 → 2 → 4 → 6. This difference is the first sign that DFS does not find shortest paths.
5.3.6DFS with a stack
Recursive DFS is short and clear, but it has a weakness: the depth of the call stack equals the length of the DFS path. In a graph containing a very long path this depth can reach tens of thousands. The call stack is a limited region of memory, and when it is exceeded Java throws StackOverflowError. In an experiment with the default settings of JDK 21, recursive DFS on a path graph with 100,000 vertices stopped with this error at a call depth of about 10,000. The remedy is to hand the call stack's job to an explicit stack object created by the program. This object lives on the heap, and its size is limited only by total memory. First, the pseudocode common in English-language sources:
procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w
in G.adjacentEdges(v) do
S.push(w)The same algorithm in a more compact form:
DFS(start):
create an empty stack
push start onto the stack
loop while the stack is not empty:
current = pop from the stack
if current is not in visited:
add current to visited
for each neighbor w of current:
push w onto the stackThe Java version:
void dfsStack(int s) {
boolean[] visited = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s);
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
visited[v] = true;
System.out.print(v + " ");
for (int w : adj[v])
stack.push(w);
}
}
}The code differs from the recursive version in three respects:
- The waiting list is explicit.
ArrayDequeis used as a stack:pushadds at the top,popremoves from the top. The loop runs until the stack is empty. - Marking happens at pop time. A vertex is marked when it is popped, not when it is pushed. A vertex that has not been popped yet can therefore be pushed several times, from different neighbors. If it is already marked when popped, nothing is done. The total number of pushes is 1 + Σ deg, which is 1 + E in a directed graph and 1 + 2E in an undirected one. The stack can grow to size O(E).
- The order reverses. Neighbors are pushed in list order, but the last one pushed comes off first. After 0, whose list is
[1, 2, 7], the first vertex popped is 7, not 1. The visit order therefore differs from that of the recursive version.
A small example shows why marking is done at pop time. Let the neighbors of 0 be 1 and 2, and let 2 have the neighbor 1. If vertices were marked when pushed, 1 and 2 would be marked together while 0 was processed. When 2 was popped, its neighbor 1 would already be marked and would not enter the stack, and 1 would be processed as the second child of 0, not from below 2. The traversal would still visit each vertex once, but the branch starting at 2 would not have been followed to its end, and the order would no longer be depth-first. Marking at pop time ensures that a vertex is processed from the place where it was discovered last. That is the "deep first" rule of DFS.
5.3.7Code trace: dfsStack(0)
Let us trace the call dfsStack(0) on the same directed graph. In the table the stack is written from left to right, bottom to top; the rightmost item is the top.
| Popped | Action | Stack after | Output |
|---|---|---|---|
| — | start: 0 is pushed | 0 | |
| 0 | mark, print; push 1, 2, 7 | 1, 2, 7 | 0 |
| 7 | mark, print; no neighbors | 1, 2 | 0 7 |
| 2 | mark, print; push 0, 3, 4 | 1, 0, 3, 4 | 0 7 2 |
| 4 | mark, print; push 6 | 1, 0, 3, 6 | 0 7 2 4 |
| 6 | mark, print; no neighbors | 1, 0, 3 | 0 7 2 4 6 |
| 3 | mark, print; push 5 | 1, 0, 5 | 0 7 2 4 6 3 |
| 5 | mark, print; push 6 | 1, 0, 6 | 0 7 2 4 6 3 5 |
| 6 | already marked, skipped | 1, 0 | 0 7 2 4 6 3 5 |
| 0 | already marked, skipped | 1 | 0 7 2 4 6 3 5 |
| 1 | mark, print; push 2 | 2 | 0 7 2 4 6 3 5 1 |
| 2 | already marked, skipped | empty | 0 7 2 4 6 3 5 1 |
The output is 0 7 2 4 6 3 5 1. The recursive version printed 0 1 2 3 5 6 4 7 on the same graph. The two orders differ, but both are valid DFS orders: the stack version gives the order that recursive DFS would give on a graph whose neighbor lists were reversed. In all, 11 pushes were made: the initial 0 and one for each of the ten edges (1 + E = 11). Vertices 6, 0, and 2 entered the stack twice each. The stack held at most four items.
If the same order as the recursive version is wanted, the neighbors are pushed in reverse order. If the neighbors of 0 are pushed in the order 7, 2, 1, then 1 ends up on top and is popped first. The two versions then produce the same visit order.
An undirected graph has the edges A–B, A–C, B–D, C–D, C–E, D–F, E–F, and F–G; the adjacency lists are in alphabetical order. Find the visit orders of recursive DFS and of stack-based DFS from A.
Recursive DFS. From A, descend to its first neighbor B. The list of B is [A, D]; A is marked, so descend to D. The list of D is [B, C, F]; B is marked, so descend to C. The list of C is [A, D, E]; A and D are marked, so descend to E. From E go to F (C is marked), from F to G (D and E are marked). The only neighbor of G, F, is marked. After that the calls return one by one and no new vertex appears. The order is A B D C E F G; the call stack reaches at most seven frames.
Stack-based DFS. Neighbors are pushed in alphabetical order:
- A is popped and printed; B and C are pushed. Stack: B, C.
- C is popped and printed; A, D, E are pushed. Stack: B, A, D, E.
- E is popped and printed; C, F are pushed. Stack: B, A, D, C, F.
- F is popped and printed; D, E, G are pushed. Stack: B, A, D, C, D, E, G.
- G is popped and printed; F is pushed. Stack: B, A, D, C, D, E, F (seven items).
- F and E are marked and skipped. D is popped and printed; B, C, F are pushed.
- F and C are skipped. B is popped and printed; A and D are pushed.
- The remaining items D, A, C, D, A, B are all marked; they are skipped one by one and the stack empties.
The order is A C E F G D B. Each vertex is processed once and pushes all its neighbors as it is processed. The adjacency lists have total length 2E = 16; together with the initial push, 17 pushes are made.
5.3.8Complexity
On a graph stored as adjacency lists, DFS runs in O(V + E) time. On a graph stored as an adjacency matrix the time is O(V2).
The cost splits into two parts. The first is the vertices. dfs is called at most once per vertex, because a call is made only for an unmarked vertex and the first thing a call does is mark its vertex. The work of each call outside the loop is constant, so the vertices contribute O(V). The second is the edges. Each call walks the adjacency list of its own vertex once and does constant work per neighbor. Since the list of each vertex is walked exactly once, the work equals the total length of all the lists. This length is E in a directed graph and 2E in an undirected one, so the edges contribute O(E). The total is O(V + E). In a matrix, finding the neighbors of a vertex means scanning a row of V cells regardless of its degree. For V vertices, V rows are scanned, giving O(V2). ∎
O(V + E) is the time needed just to read the graph. Nothing can be said about the whole graph without looking at every vertex and every edge at least once. This bound is therefore the best possible for traversal, and algorithms of this kind are called linear-time graph algorithms.
Extra memory also has two parts. The array visited[] takes O(V) space. The size of the stack depends on the version. In the recursive version the call stack goes as deep as the longest path in the DFS tree, which is V in the worst case, so O(V). On a path graph (0–1–2–…), for example, the stack holds all vertices. In the stack-based version that marks at pop time, a vertex can be pushed several times, so the stack can grow to O(E). In a dense graph E can be of order V2, so this difference is not negligible. A more elaborate version that avoids the duplicates on the stack can also be written. In it, each stack item holds, together with the vertex, the index of the next neighbor to try. This imitates recursive DFS exactly, and O(V) extra memory suffices.
5.3.9What DFS is good for, and what it cannot do
The power of DFS comes from the structural information it collects during the traversal. When a vertex was discovered, when it finished, and whether an edge leads to a yellow or a dark vertex are enough to answer many questions:
- Reachability and connected components. After a DFS from s, t is reachable if
visited[t]is true. The number of times DFS is started gives the number of connected components of an undirected graph. - Cycle detection. In a directed graph, an edge to a vertex on the call stack (a yellow vertex) is called a back edge. A back edge, together with the tree path from its target down to its source, forms a cycle. Conversely, if the graph has a cycle, all the other vertices of the cycle are discovered before the first-discovered vertex of the cycle finishes, and the cycle's edge back to that vertex is a back edge. A directed graph therefore has a cycle exactly when DFS finds a back edge.
- Topological sorting. In a directed acyclic graph, reversing the finishing order of the vertices gives a topological order.
- Strongly connected components. The algorithms of Tarjan and Kosaraju are built on DFS.
- Bridges and articulation points, puzzle solving. Bridges are found with Tarjan's low-link idea. Backtracking algorithms that solve puzzles such as Sudoku and the eight queens problem are also DFS on an implicit graph.
What DFS cannot do is just as important: DFS does not find shortest paths. The path DFS follows when it first reaches a target can be a long detour. In the directed example DFS reached 6 by the path 0 → 1 → 2 → 3 → 5 → 6, in five edges; the shortest path had three. In the undirected graph of Example 5.3 the DFS tree follows the path A–B–D–C–E–F–G from A to G, six edges; the shortest path is A–B–D–F–G, four edges. Finding the path with the fewest edges requires breadth-first search.
5.4Breadth-first search (BFS)
While DFS follows one branch to its end, BFS advances all branches together, step by step. The difference looks small, but it has an important consequence: in an unweighted graph, BFS finds the path with the fewest edges from the start to every vertex. The route with the fewest transfers in navigation, the length of the chain of acquaintance between two people in a social network, and the solution in the fewest moves in a game are all computed this way.
5.4.1The idea: layer by layer
The ripples made by a stone dropped into still water describe BFS well. The wave first reaches the immediate surroundings of the stone, then one ring further out, then another. News spreads the same way: the person who receives it tells all their friends, and they tell their own friends. The first to hear are those one step away from the start, then those two steps away.
Breadth-first search (BFS) visits the vertices reachable from the start vertex s in order of their distance from s: first s, then the vertices one edge away, then those two edges away. Discovered vertices wait in a queue; the first-in, first-out rule of the queue preserves this order.
The levels of BFS are defined as follows: L0 = {s}; L1 is the set of neighbors of s; in general Lk+1 is the set of neighbors of vertices in Lk that are in no level yet. The distance of every vertex in Lk from s, that is, the number of edges of a shortest path from s to it, is exactly k.
BFS has two rules. First, the queue preserves order: the vertex discovered first is processed first. All vertices in L1 enter the queue before those in L2, so they leave first. Second, a vertex is marked when it enters the queue. This way a vertex enters the queue at most once, even if several neighbors see it. This rule is the opposite of the "mark at pop time" rule of stack-based DFS; its purpose is to keep the queue from growing needlessly.
5.4.2An example with levels
Take an undirected graph on eight vertices: vertex 1 is joined to 2, 3, 4, and 5; vertex 2 to 6 and 7; vertex 3 to 8. BFS starts at 1. Table 5.6 shows, at each step, the vertex taken from the queue, the vertices added, and the state of the queue.
| Step | Taken | Newly discovered | Queue | Level |
|---|---|---|---|---|
| 0 | — | 1 | 1 | 1 → L0 |
| 1 | 1 | 2, 3, 4, 5 | 2, 3, 4, 5 | 2, 3, 4, 5 → L1 |
| 2 | 2 | 6, 7 | 3, 4, 5, 6, 7 | 6, 7 → L2 |
| 3 | 3 | 8 | 4, 5, 6, 7, 8 | 8 → L2 |
| 4 | 4 | — | 5, 6, 7, 8 | |
| 5 | 5 | — | 6, 7, 8 | |
| 6 | 6 | — | 7, 8 | |
| 7 | 7 | — | 8 | |
| 8 | 8 | — | empty |
The visit order is 1, 2, 3, 4, 5, 6, 7, 8. The vertices at distance 1 (2, 3, 4, 5) come first, then those at distance 2 (6, 7, 8). Vertices 6 and 7 were discovered before 3 was processed, but because they were added at the end of the queue they are processed after 3, 4, and 5. The next level is not started before the whole of one level is done; this is what "layer by layer" means for BFS. In this example the graph is a tree, and the edges that discover each vertex are all the edges of the graph.
5.4.3Pseudocode
procedure BFS(G, root) is
let Q be a queue
label root as explored
Q.enqueue(root)
while Q is not empty do
v := Q.dequeue()
for all edges from v to w
in G.adjacentEdges(v) do
if w is not labeled as explored then
label w as explored
w.parent := v
Q.enqueue(w)A more compact form:
BFS(start):
create an empty queue
mark start as explored
put start in the queue
loop while the queue is not empty:
current = take from the queue
for each neighbor w of current:
if w is not explored:
mark w as explored
parent of w = current
put w in the queueTwo details of the pseudocode matter. The first is the line w.parent := v: every vertex records the vertex that discovered it as its parent. These parent links form a tree, called the BFS tree. Following parents from the target back to the root yields, in reverse, the shortest path from the start to the target. The second is that marking is done when a vertex is added to the queue, not when it is removed. Otherwise a vertex would be added again by every neighbor that sees it during the time before it leaves the queue.
5.4.4Code: bfs()
void bfs(int s) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
visited[s] = true; queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int w : adj[v])
if (!visited[w]) {
visited[w] = true;
queue.add(w);
}
}
}boolean[] visited = new boolean[n];starts with all vertices unmarked. Java arrays are created filled withfalse.Queue<Integer> queue = new LinkedList<>();creates the queue.LinkedListimplements theQueueinterface;addappends at the end andpollremoves from the front, both in O(1).ArrayDequedoes the same job.visited[s] = true; queue.add(s);marks the start and puts it in the queue. The mark is set at the same moment as the entry into the queue.int v = queue.poll();removes the vertex at the front of the queue, which is then printed. Because vertices are printed in the order they leave the queue, the output is the BFS visit order.- The inner loop walks over the neighbors of v. An unmarked neighbor is marked and appended to the queue; a marked neighbor is skipped.
The time analysis is the same as for DFS. Each vertex enters the queue at most once and leaves once: O(V). The adjacency list of each vertex is walked once, when the vertex leaves the queue: O(E) in total. BFS runs in O(V + E) time with adjacency lists and in O(V2) with a matrix. The extra memory is O(V) for visited[] and as much as the widest level for the queue, which is O(V) in the worst case.
5.4.5Code trace: bfs(0)
Let us run the code on the directed graph used in the DFS trace: adj[0] = [1, 2, 7], adj[1] = [2], adj[2] = [0, 3, 4], adj[3] = [5], adj[4] = [6], adj[5] = [6]; 6 and 7 have no neighbors.
Taken v | Neighbor scan | Queue (after) | Output |
|---|---|---|---|
| — | 0 is marked and enters the queue | 0 | |
| 0 | 1, 2, 7 unmarked → mark, add | 1, 2, 7 | 0 |
| 1 | 2 marked → skip | 2, 7 | 0 1 |
| 2 | 0 marked → skip; 3, 4 → mark, add | 7, 3, 4 | 0 1 2 |
| 7 | no neighbors | 3, 4 | 0 1 2 7 |
| 3 | 5 → mark, add | 4, 5 | 0 1 2 7 3 |
| 4 | 6 → mark, add | 5, 6 | 0 1 2 7 3 4 |
| 5 | 6 marked → skip | 6 | 0 1 2 7 3 4 5 |
| 6 | no neighbors | empty | 0 1 2 7 3 4 5 6 |
bfs(0) finishes, the thick edges form the BFS tree: 0→1, 0→2, 0→7, 2→3, 2→4, 3→5, 4→6. The tree is shallower and wider than the DFS tree.The output is 0 1 2 7 3 4 5 6 and the levels are {0}, {1, 2, 7}, {3, 4}, {5, 6}. Vertex 2 is also seen as a neighbor of 1, but it was already marked while 0 was processed, so it does not enter the queue a second time. The same holds for 6: 4 marked and added it, and 5 merely sees it. The queue held at most three vertices. The distance of 6 is 3 (0 → 2 → 4 → 6); the DFS tree had reached the same vertex in five edges.
Marking a vertex when it is removed from the queue in BFS. In that case an unmarked vertex is added again by every neighbor that sees it while it waits in the queue. The result is often still correct, because a removed vertex is skipped if marked, but the queue grows needlessly. On the complete graph with five vertices, correct BFS from 0 makes 5 insertions and the queue holds at most 4 vertices. The version that marks on removal makes 11 insertions on the same graph and the queue reaches 7 vertices. In general the number of insertions rises from O(V) to O(E). The right way is to mark on insertion.
5.4.6Distance and parent arrays
To use the shortest-path property of BFS, two arrays are kept in place of the visited array. dist[v] holds the least number of edges from s to v; the parent array (parent[] in the code) holds the parent of v in the BFS tree, that is, the vertex that discovered v. dist[v] == -1 means "not discovered yet", so a separate visited[] array is not needed.
void bfsDist(int s) {
Arrays.fill(dist, -1);
Arrays.fill(parent, -1); dist[s] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : adj[v])
if (dist[w] == -1) { /* new */
dist[w] = dist[v] + 1;
parent[w] = v;
queue.add(w);
}
}
}Arrays.fill(dist, -1);treats all vertices as undiscovered.Arrays.fill(parent, -1); dist[s] = 0;sets all parents to "none" (−1) and sets the distance of the start to 0. The parent of the start also stays −1; when a path is built, this value shows that the root has been reached. Filling all ofparent[]makes unreachable vertices carry −1 too; we will see below why this is needed when building a path.if (dist[w] == -1)asks whether the neighbor is new. For a new neighbor,dist[w] = dist[v] + 1is written: w is in the level after the level of v.parent[w] = vrecords that w was reached from v.
Let us trace the code on the undirected example graph numbered 1 to 8 (1–2, 1–3, 1–4, 1–5, 2–6, 2–7, 3–8). In the table the arrays are written with indices 1–8; "—" is an undiscovered vertex (dist = −1, parent = −1).
| Taken | Queue (after) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| — | 1 | 0/−1 | — | — | — | — | — | — | — |
| 1 | 2, 3, 4, 5 | 0/−1 | 1/1 | 1/1 | 1/1 | 1/1 | — | — | — |
| 2 | 3, 4, 5, 6, 7 | 0/−1 | 1/1 | 1/1 | 1/1 | 1/1 | 2/2 | 2/2 | — |
| 3 | 4, 5, 6, 7, 8 | 0/−1 | 1/1 | 1/1 | 1/1 | 1/1 | 2/2 | 2/2 | 2/3 |
| 4, 5, 6, 7, 8 | empty | no change: the only neighbor of each has already been discovered | |||||||
When 2 is taken from the queue, its neighbor 1 has already been discovered (dist[1] = 0), so it is skipped. 6 and 7 are new and get the value dist[2] + 1 = 2. When the queue is empty the result is as in Table 5.9.
| vertex | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| distance | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| parent | — | 1 | 1 | 1 | 1 | 2 | 2 | 3 |
bfsDist(1) finishes, the thick edges are the parent links and form the BFS tree. For example, the parent of 8 is 3 and the parent of 3 is 1; the shortest path from 1 to 8 is 1 → 3 → 8, with length dist[8] = 2.The distances of the vertices leaving the queue are, in order, 0, 1, 1, 1, 1, 2, 2, 2; the sequence never decreases. This is the key property of BFS and is used in the proof of the shortest-path theorem.
5.4.7Unweighted shortest paths
In an unweighted graph, after BFS from s, for every v reachable from s, dist[v] equals the number of edges of a shortest path from s to v. Following the parent links from v to s yields a path of this length.
Two observations come first. (1) The distance of every vertex entering the queue is one more than that of the vertex that adds it. (2) At every moment the distances in the queue are in nondecreasing order, and the difference between the first and the last item is at most 1. The second observation follows by induction: at the start the queue holds only s. When the vertex at the front, with distance d, is removed and new vertices are appended with distance d + 1, the smallest value in the queue is at least d and the largest is at most d + 1. Now the theorem itself. It is clear that for any v, dist[v] cannot be smaller than the true shortest distance δ(v), because the parent chain is a real path from s to v with dist[v] edges. To show the converse, take a v with dist[v] > δ(v) whose δ value is smallest. Let u be the vertex before v on a shortest path from s to v; then δ(u) = δ(v) − 1, and by the choice of v, dist[u] = δ(u). If v has not been discovered yet when u is removed from the queue, u discovers it and dist[v] = δ(u) + 1 = δ(v), a contradiction. If v was discovered earlier, the vertex that added it was removed from the queue before u. By observation (2) the distance of that vertex is at most δ(u); then dist[v] ≤ δ(u) + 1 = δ(v), again a contradiction. ∎
In plain words, the theorem says: at the moment BFS first reaches a vertex, it has reached it by a shortest path. If a shorter path existed, the vertex before the last on that path would have left the queue earlier and discovered the target earlier. BFS therefore writes the distance of a vertex once and never corrects it.
The path itself is rebuilt from the parent array:
List<Integer> path(int[] parent, int s, int t) {
LinkedList<Integer> path = new LinkedList<>();
for (int v = t; v != -1; v = parent[v])
path.addFirst(v); /* from target back */
if (path.getFirst() != s)
return null; /* t unreachable */
return path;
}The loop starts at the target t and moves to the parent at each step, stopping when it reaches −1. Because the vertices are found from the target toward the source, each is added at the front of the list (addFirst); the list then comes out ordered from source to target. For source 1 and target 8 the loop adds 8, moves to parent[8] = 3, adds 3, moves to parent[3] = 1, adds 1, and stops at parent[1] = −1. The list is [1, 3, 8]; its first item is the source, so the path is returned. The path has dist[t] + 1 vertices, so building it takes O(dist[t]) time.
The final if catches the case where the target was never reached. If t was not discovered, parent[t] = −1; the loop adds only t and stops. The first item of the list is t, not s, and the method returns null. This check works correctly only because parent[] is filled with −1 at the start of BFS.
Filling only dist[] with −1 in BFS and leaving parent[] at Java's default values. An int array is created with 0s, so for an unreachable t the entry parent[t] = 0 remains and the path-building loop moves from t to 0. If the source is 0, the loop builds the list [0, t] and returns a path that does not exist. For example, in a graph with four vertices and the edges 0–1 and 1–3, there is no edge to 2, yet after a BFS from 0 the call path(parent, 0, 2) returns [0, 2]. If the source is not 0 and 0 is also unreachable, the loop spins on 0 forever. When parent[] is also filled with −1, the same call correctly returns null.
The theorem holds only in an unweighted graph, or one in which all weights are equal. BFS minimizes the number of edges, not the sum of weights. Take a graph with the edges s → t (weight 10), s → a (weight 1), and a → t (weight 1). BFS finds t in the first level, as a direct neighbor of s. The path found has a single edge but costs 10. The cheapest path is s → a → t, with cost 2. For shortest paths in a weighted graph, Dijkstra's algorithm is needed.
5.4.8Solving a maze with BFS
A grid maze can be turned into a graph directly. Every open cell is a vertex. There is an edge between two open cells that are adjacent above, below, to the right, or to the left. Wall cells do not enter the graph at all. The question "fewest steps from entrance to exit" thus becomes "shortest path between two vertices in this graph". The graph is unweighted, since every step costs the same; the right tool is BFS.
The maze in Figure 5.14 has 9 × 9 cells. Of the cells, 47 are walls and 34 are open; the number of adjacent pairs of open cells is also 34. The graph has 34 vertices and 34 edges. The entrance is at the top left and the exit at the bottom right. The neighbors of a vertex are the open cells in the four directions. The neighbors are not stored in a separate list in the code; the row and column numbers of a cell's four neighbors are computed directly. A graph defined this way is called an implicit graph.
The traversal goes like this. The entrance cell is put in the queue with distance 0. In the first steps the maze is a single corridor and the wave descends; the number written in each cell is one more than the previous one. At the cell with distance 5 the path forks. The wave now splits into two arms: one goes to the right and from there to the room above, the other goes down. BFS advances these two arms not one after the other but together; in the queue the cells of distance 6 from both arms wait side by side, followed by the cells of distance 7. For this reason BFS is also described as a search that "tries all existing paths simultaneously".
At distance 10 the wave reaches both the corridor above and the lower corridor below. While the upper arm wanders in dead ends for a while, the lower corridor approaches the exit. The exit cell is reached in 14 steps. By the theorem this value is exactly the shortest; had a shorter path existed, the exit would have been discovered in an earlier level. The search can stop at this point. If it does not, six more cells with distances 15, 16, and 17 are discovered; these are unnecessary for the shortest path. The shortest path is found by starting at the exit and following the parent links back to the entrance. The path consists of 15 cells, that is, 14 steps.
DFS also finds the exit in the same maze, but the path it finds is not guaranteed to be the shortest. If at the fork it enters the upper arm first, it may reach the exit by a long detour after going through all the dead ends of that arm. The price of BFS is memory: it holds the whole frontier of the wave in the queue at once.
5.4.9Comparing BFS and DFS
| DFS | BFS | |
|---|---|---|
| Auxiliary structure | Stack (LIFO) or recursion | Queue (FIFO) |
| Traversal pattern | Follows one branch to its end, then backs up | Layer by layer, in order of distance |
| Time | O(V + E) with lists; O(V2) with a matrix | O(V + E) with lists; O(V2) with a matrix |
| Extra memory | O(V): the longest path is on the stack | O(V): the widest level is in the queue |
| Shortest path | No | Yes (in an unweighted graph) |
| Tree produced | Deep and thin | Shallow and wide |
| Typical uses | Cycles, components, topological order, SCCs, backtracking | Fewest steps, levels, bipartiteness test, spreading |
On the same directed graph, from the same source 0, DFS prints 0 1 2 3 5 6 4 7 and BFS prints 0 1 2 7 3 4 5 6. Both visit every vertex once and have the same running time; the difference lies in the visit order and in the trees they produce.
The memory comparison depends on the shape of the graph. Traverse a complete binary tree with 15 vertices (four levels) from the root. In BFS the eight leaves of the last level are in the queue at the same time; the queue holds at most 8 vertices. In recursive DFS the call stack goes as deep as the path from the root to a leaf, 4 frames. If the tree had 20 levels, that is 1,048,575 vertices, the BFS queue would reach 524,288 vertices while the DFS stack would stay at 20 frames. Conversely, on a long path graph the DFS stack holds all the vertices, while the BFS queue holds a single vertex if it starts at an end. The worst case of both is O(V); which uses less memory is determined by the depth and width of the graph.
In the undirected graph of Example 5.3 (A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G; neighbors in alphabetical order), find the BFS visit order from A, the distances, and the shortest path from A to G.
- A is marked and enters the queue. Queue: A.
- A is taken; B and C are discovered (distance 1, parent A). Queue: B, C.
- B is taken; A is marked, D is discovered (distance 2, parent B). Queue: C, D.
- C is taken; A and D are marked, E is discovered (distance 2, parent C). Queue: D, E.
- D is taken; B and C are marked, F is discovered (distance 3, parent D). Queue: E, F.
- E is taken; C and F are marked. Queue: F.
- F is taken; D and E are marked, G is discovered (distance 4, parent F). Queue: G.
- G is taken; F is marked. The queue empties.
The visit order is A B C D E F G. The distances are A 0, B 1, C 1, D 2, E 2, F 3, G 4. F was discovered by D, not E, because D leaves the queue before E. Following parents from G: the parent of G is F, of F is D, of D is B, of B is A. Reversed, this gives the shortest path A–B–D–F–G, four edges long. The path A–B–D–C–E–F–G that DFS followed on the same graph has six edges.
5.5Strongly connected components
In an undirected graph connectivity is a simple notion: if there is a path from u to v, there is one from v to u. In a directed graph this symmetry breaks. In a city full of one-way streets one can get from one neighborhood to another and yet be unable to return the same way. Finding which vertices can reach each other in both directions is the first step toward understanding the structure of directed graphs.
5.5.1Definition
In a directed graph, u and v are mutually reachable if there is a path from u to v and a path from v to u. A maximal set of vertices in which every vertex can reach every other, and which cannot be enlarged without losing this property, is a strongly connected component (SCC).
The edges of the graph in Figure 5.15 are 1→2, 2→3, 3→1, 4→2, 4→3, 4→5, 5→6, 5→4, 6→3, 6→7, 7→6, 8→5, 8→7, and 8→8. Vertices 1, 2, and 3 lie on a cycle (1 → 2 → 3 → 1); each reaches the others. There are edges in both directions between 4 and 5, and between 6 and 7. Vertex 8 is a component by itself: every other vertex is reachable from 8, but 8 is reachable from no vertex.
A few consequences follow from the definition. Mutual reachability is an equivalence relation: every vertex reaches itself (a path of length zero), the relation is symmetric, and it is transitive (if u ⇄ v and v ⇄ w then u ⇄ w). Strongly connected components therefore partition the vertex set into disjoint parts; every vertex belongs to exactly one component. A single vertex can also be a component; every vertex that takes part in no cycle is one.
A common misconception is to take "a vertex together with all vertices reachable from it" as a component. All vertices are reachable from 8, but {1, …, 8} is not an SCC, because, for example, there is no way back from 1 to 8. An SCC requires reachability in both directions.
If each component is contracted to a single vertex and the edges between components are kept, the result is the component graph. In the example in the figure its edges are {8} → {4, 5}, {8} → {6, 7}, {4, 5} → {1, 2, 3}, {4, 5} → {6, 7}, and {6, 7} → {1, 2, 3}. The component graph is always acyclic. If there were paths in both directions between two components, the vertices of these components would be mutually reachable, and the two components would in fact be one. This structure is used in many applications: finding communities of people who follow each other in social networks, compiling mutually dependent modules of a compiler together, solving the 2-SAT problem in logic, and others.
The crudest way to find the components is to run a traversal from every vertex and test mutual reachability one pair at a time; this takes O(V · (V + E)) time. In 1972 Robert Tarjan published an algorithm that finds all components with a single DFS, in O(V + E) time.
5.5.2The idea behind Tarjan's algorithm
Tarjan's algorithm assigns two numbers to each vertex during DFS and keeps the discovered vertices in a separate stack.
index(v) is the discovery order of v: the first discovered vertex has index 1, the second 2. low(v), the low-link value of v, is the smallest index reachable from the DFS subtree of v using at most one non-tree edge to a vertex that is still on the stack. Initially low(v) = index(v).
This stack differs from the DFS call stack. A vertex is pushed onto it when it is discovered, but it is not popped as soon as its work is finished. It stays on the stack until its component has been determined. The stack therefore holds the vertices that have been discovered so far and not yet assigned to any component.
While examining the edges of a vertex v, DFS meets three cases:
- Tree edge v → w, with w not yet discovered: continue recursively from w. When the call returns, set low(v) = min(low(v), low(w)). If the subtree of w can reach an older vertex, so can v.
- An edge to a vertex w on the stack: w has been discovered and not yet assigned to a component. Set low(v) = min(low(v), index(w)). Vertex v can reach a vertex that was discovered before it and whose component is still open.
- An edge to a vertex w whose component has been found: w has been discovered and popped from the stack. This edge is ignored. The component of w is closed; there is no path from w back to v, and v cannot join that component.
The decision is made after all edges of v have been examined. If low(v) = index(v), then no vertex on the stack older than v can be reached from the subtree of v. Vertex v is the root of a component, that is, the first vertex discovered in that component. All the vertices popped from the stack down to v (including v) form an SCC. If low(v) < index(v), an older stack vertex can be reached back from the subtree of v; v is in the same component as that vertex and is not a root. Vertex v stays on the stack and its component is popped together when the root finishes.
The root condition can be justified briefly as follows. Let r be the first vertex discovered in a component. All other vertices of the component are reachable from r, so they fall in the subtree of r and are discovered before r finishes. No vertex of the component can reach a stack vertex older than r; if one could, that vertex would reach r, r would reach it, and it would be in the same component. So low(r) = index(r) remains. The other vertices of the component, since they can return to r, get a smaller low-link value.
5.5.3Tarjan step by step
On the graph of Figure 5.15, Tarjan's algorithm tries the vertices in order from 1 to 8. Indices start at 1. Next to each vertex we write the pair "index, low". Table 5.11 gives all the steps of the algorithm.
| Step | Event | Stack (after) | SCC found |
|---|---|---|---|
| 1 | SCC(1): index = low = 1 | 1 | |
| 2 | 1 → 2 tree edge; SCC(2): 2, 2 | 1, 2 | |
| 3 | 2 → 3 tree edge; SCC(3): 3, 3 | 1, 2, 3 | |
| 4 | 3 → 1: 1 is on the stack → low(3) = min(3, 1) = 1 | 1, 2, 3 | |
| 5 | 3 finishes; 1 < 3, not a root. Back at 2: low(2) = min(2, 1) = 1 | 1, 2, 3 | |
| 6 | 2 finishes, not a root. Back at 1: low(1) = 1. At 1, low = index → root | empty | {1, 2, 3} |
| 7 | SCC(4): 4, 4 | 4 | |
| 8 | 4 → 2 and 4 → 3 ignored (components found); 4 → 5: SCC(5): 5, 5 | 4, 5 | |
| 9 | 5 → 6: SCC(6): 6, 6 | 4, 5, 6 | |
| 10 | 6 → 3 ignored; 6 → 7: SCC(7): 7, 7 | 4, 5, 6, 7 | |
| 11 | 7 → 6: 6 is on the stack → low(7) = min(7, 6) = 6 | 4, 5, 6, 7 | |
| 12 | 7 finishes, not a root. Back at 6: low(6) = 6 unchanged; 6 is a root | 4, 5 | {6, 7} |
| 13 | Back at 5: low(5) = min(5, 6) = 5. 5 → 4: 4 is on the stack → low(5) = min(5, 4) = 4 | 4, 5 | |
| 14 | 5 finishes, not a root. Back at 4: low(4) = min(4, 4) = 4; 4 is a root | empty | {4, 5} |
| 15 | SCC(8): 8, 8 | 8 | |
| 16 | 8 → 5 and 8 → 7 ignored; self-loop 8 → 8: 8 is on the stack, low = min(8, 8) = 8 | 8 | |
| 17 | At 8, low = index → root | empty | {8} |
Three moments in the table show the whole logic of the algorithm. In step 4 the edge 3 → 1 catches a return to an older vertex on the stack and lowers the low-link of 3 to 1. This value is carried to 2 and to 1 by the call returns in steps 5 and 6. In the end only 1 has index equal to low; 1 is a root, and every vertex above 1 on the stack is in its component.
In step 8 the edges 4 → 2 and 4 → 3 are ignored. Vertices 2 and 3 have been discovered but are not on the stack; their components are closed. Had these edges been taken into account, the low-link of 4 would have dropped to 2 and 4 would not have been counted as a root. Yet although 4 reaches 2, there is no path from 2 back to 4; 4 is the first vertex of a new component.
In step 12, 6 is found to be a root and {6, 7} is popped, but 5 and 4 stay on the stack. The component of 5 and 4 is closed later, in step 14. The components are found in the order {1, 2, 3}, {6, 7}, {4, 5}, {8}. Comparing with the edges of the component graph shows that this order is a reverse topological order: each component is found before all components that have edges into it. No edge leaves {1, 2, 3}, and it is found first; no edge enters {8}, and it is found last. This is no coincidence: a component can close only after all the components reachable from it have been found.
5.5.4Pseudocode and Java code
The pseudocode of the algorithm has two parts. The outer loop calls SCC from every unvisited vertex:
TARJAN_SCC(G):
index = 1
stack = [ ]
sccs = [ ]
for each v in V:
if v.index is not defined:
SCC(v)
return sccsThe real work is in the recursive procedure SCC:
SCC(v):
v.index = v.low = index++
stack.push(v)
for each (v, w) in E:
if w.index is not defined:
SCC(w)
v.low = min(v.low, w.low)
else if w is on the stack:
v.low = min(v.low, w.index)
if v.low == v.index:
scc = [ ]
repeat until w == v:
w = stack.pop()
scc.add(w)
sccs.add(scc)The Java code is a direct counterpart of the pseudocode:
void scc(int v) {
index[v] = low[v] = ++counter;
stack.push(v); onStack[v] = true;
for (int w : adj[v]) {
if (index[w] == 0) {
scc(w);
low[v] = Math.min(low[v], low[w]);
} else if (onStack[w])
low[v] = Math.min(low[v], index[w]);
}
if (low[v] == index[v]) {
int w;
do {
w = stack.pop(); onStack[w] = false;
System.out.print(w + " ");
} while (w != v);
System.out.println();
}
}index[v] = low[v] = ++counter;assigns the discovery order.counterstarts at 0 and is incremented first, so the first vertex gets index 1. This choice lets the testindex[w] == 0mean "not discovered yet", so no separate visited array is needed. Starting the indices at 0 gives the same components; then another marker, for example −1, is needed for undiscovered vertices.stack.push(v); onStack[v] = true;pushes the vertex. The arrayonStack[]answers the question "is w on the stack?" in O(1) time. Searching the stack from end to end would take O(V) at every edge.- The branch
if (index[w] == 0)is the tree edge: after the recursive call,low[v]is updated withlow[w]. - The branch
else if (onStack[w])is the edge to a vertex on the stack:low[v]is updated withindex[w]. For a w whose component has been found, both conditions are false and nothing is done. - The last
ifis the root test. Thedo … whileloop pops all vertices from the stack down to v and prints them. The loop is of thedo … whileform because at least one vertex (v itself) is always popped. Each component is written on a separate line.
5.5.5Code trace: scc(0)
The graph in the trace has five vertices: 0→1, 1→2, 2→0, 2→3, 3→4, 4→3. adj[2] = [0, 3].
| Step | Event | Changed value | Stack (after) | Output |
|---|---|---|---|---|
| 1 | scc(0) | 0: 1/1 | 0 | |
| 2 | 0 → 1 undiscovered → scc(1) | 1: 2/2 | 0, 1 | |
| 3 | 1 → 2 undiscovered → scc(2) | 2: 3/3 | 0, 1, 2 | |
| 4 | 2 → 0: 0 is on the stack | low[2] = min(3, 1) = 1 | 0, 1, 2 | |
| 5 | 2 → 3 undiscovered → scc(3) | 3: 4/4 | 0, 1, 2, 3 | |
| 6 | 3 → 4 undiscovered → scc(4) | 4: 5/5 | 0, 1, 2, 3, 4 | |
| 7 | 4 → 3: 3 is on the stack | low[4] = min(5, 4) = 4 | 0, 1, 2, 3, 4 | |
| 8 | low[4] = 4 ≠ index[4] = 5: not a root, returns | 0, 1, 2, 3, 4 | ||
| 9 | scc(4) returned | low[3] = min(4, 4) = 4 | 0, 1, 2, 3, 4 | |
| 10 | low[3] == index[3] = 4: 3 is a root; 4 and 3 are popped | 0, 1, 2 | 4 3 | |
| 11 | scc(3) returned | low[2] = min(1, 4) = 1 | 0, 1, 2 | 4 3 |
| 12 | low[2] = 1 ≠ 3: not a root, returns | low[1] = min(2, 1) = 1 | 0, 1, 2 | 4 3 |
| 13 | low[1] = 1 ≠ 2: not a root, returns | low[0] = min(1, 1) = 1 | 0, 1, 2 | 4 3 |
| 14 | low[0] == index[0] = 1: 0 is a root; 2, 1, 0 are popped | empty | 4 3 / 2 1 0 |
index/low values.The program prints two lines: first 4 3, then 2 1 0. Vertices within a component are printed in the order they are popped from the stack, that is, the reverse of discovery order. The edge 2 → 0 in step 4 is a back edge and lowers low[2] to 1. In step 11, when scc(3) returns, the value low[3] = 4 does not change that of 2, since 2 has already reached 1. The component {3, 4} is reachable from 2 but cannot return to 2, and it closes first.
Let the directed graph have the edges 0→1, 1→2, 2→0, 1→3, 3→4, 4→5, 5→3, 5→6 (adj[1] = [2, 3], adj[5] = [3, 6]). Tarjan's algorithm is started at 0 and indices start at 1.
- Vertices 0, 1, 2 are discovered in order: indices 1, 2, 3. The edge 2 → 0 goes to 0 on the stack;
low[2] = 1. Vertex 2 is not a root; on return,low[1] = 1. - 1 → 3 is a tree edge. Vertices 3, 4, 5 are discovered in order: indices 4, 5, 6. The edge 5 → 3 goes to 3 on the stack;
low[5] = 4. - 5 → 6 is a tree edge; the index of 6 is 7. Vertex 6 has no outgoing edges,
low[6] = index[6] = 7: 6 is a root. The first component is {6}. - Back at 5:
low[5] = min(4, 7) = 4; 5 is not a root. Return to 4 giveslow[4] = 4, return to 3 giveslow[3] = 4. At 3, index and low-link are equal: the second component is {3, 4, 5}. - Back at 1:
low[1] = min(1, 4) = 1. Back at 0, and 0 is a root: the third component is {0, 1, 2}.
The components are found in the order {6}, {3, 4, 5}, {0, 1, 2}. The component graph is {0, 1, 2} → {3, 4, 5} → {6}; the order of discovery is its reverse.
5.5.6Complexity
On a graph stored as adjacency lists, Tarjan's algorithm finds all strongly connected components in O(V + E) time and O(V) extra memory.
The algorithm is a DFS, and the DFS count applies unchanged. scc is called once for each vertex; each vertex is pushed once and popped once. The work per vertex is constant: O(V). Each edge is examined once, when the adjacency list of its source is walked, and the work done in each examination (one min and an onStack[] test) is constant: O(E). The total number of iterations of the popping loop is the number of popped vertices, that is, V. The extra memory is O(V) for the arrays index, low, onStack and for the stack, and again O(V) for the recursion depth. ∎
Skipping the test else if (onStack[w]) in Tarjan's code and doing low[v] = min(low[v], index[w]) for every discovered w. An edge to a vertex whose component has been found is then wrongly counted as a "return". In the eight-vertex example the edge 4 → 2 would lower low(4) to 2, the edge 6 → 3 would lower low(6) to 3, and the edge 8 → 5 would lower low(8) to 5. Vertices 4, 6, and 8 would no longer be counted as roots. The first component {1, 2, 3} would still be found correctly, but {4, 5}, {6, 7}, and {8} would never be popped; all the vertices from 4 to 8 would remain on the stack when the algorithm ends.
5.5.7Kosaraju's algorithm
The second classical method for strongly connected components is Kosaraju's algorithm. It is easier to understand than Tarjan's, but it needs two DFS passes and a copy of the graph. The algorithm works on the transpose of a graph: the transpose has the same vertices, and each edge u → v becomes v → u. A graph and its transpose have the same strongly connected components, because mutual reachability is not affected by the direction of the arrows.
The algorithm has three steps:
- Run DFS on the graph and push each vertex onto a stack when it finishes. The vertex that finished last sits on top of the stack.
- Build the transpose of the graph.
- Pop vertices from the stack in order. If the popped vertex has not been visited yet, run a DFS from it in the transpose. The vertices this DFS reaches form an SCC.
The part that builds the transpose:
List<Integer>[] rev = new List[n];
for (int v = 0; v < n; v++)
rev[v] = new ArrayList<>();
for (int v = 0; v < n; v++)
for (int w : adj[v])
rev[w].add(v); /* edge v to w becomes w to v */The Java code of the algorithm:
void kosaraju() {
for (int v = 0; v < n; v++) /* pass 1 */
if (!visited[v]) dfs1(v);
Arrays.fill(visited, false); /* pass 2 */
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) { /* new SCC */
dfs2(v); System.out.println(); }
}
}
void dfs1(int v) {
visited[v] = true;
for (int w : adj[v])
if (!visited[w]) dfs1(w);
stack.push(v); /* v finished */
}dfs2 in the second pass is an ordinary DFS running on the transpose:
void dfs2(int v) { /* DFS on transpose */
visited[v] = true;
System.out.print(v + " ");
for (int w : rev[v])
if (!visited[w]) dfs2(w);
}dfs1 differs from dfs by a single line: a vertex is pushed onto the stack after all its neighbors have finished (stack.push(v); /* v finished */). This line records the finishing order. kosaraju() first starts dfs1 from every unvisited vertex. Then it clears the visited array and empties the stack. Every unvisited vertex popped from the stack is the start of a new component.
Why the algorithm is correct is explained with the component graph. The vertex that finishes last in the first pass lies in a source component, one with no incoming edges in the component graph. In the transpose all the outgoing edges of this component turn inward. A DFS started from it in the transpose therefore cannot leave the component and traverses exactly that component. The next unvisited vertex on the stack lies, among the remaining components, again in a source component. In the transpose the edges leaving it go either to its own component or to components already found; visited vertices are not entered either. Thus each DFS finds exactly one component.
Let us trace Kosaraju's algorithm on the five-vertex graph of the Tarjan trace (0→1, 1→2, 2→0, 2→3, 3→4, 4→3).
| Pass | Event | Stack (after) | SCC found |
|---|---|---|---|
| 1 | dfs1(0) → dfs1(1) → dfs1(2); 2 → 0 visited, skipped; dfs1(3) → dfs1(4) | empty | |
| 1 | The only neighbor of 4, 3, is visited: 4 finishes, is pushed | 4 | |
| 1 | 3 finishes, is pushed | 4, 3 | |
| 1 | 2, 1, 0 finish in order and are pushed | 4, 3, 2, 1, 0 | |
| 2 | 0 is popped; in the transpose dfs2(0): 0 → 2 → 1 | 4, 3, 2, 1 | {0, 2, 1} |
| 2 | 1 and 2 are popped; visited, skipped | 4, 3 | |
| 2 | 3 is popped; dfs2(3): the reversed edge 3 → 2 goes to visited 2; 3 → 4 | 4 | {3, 4} |
| 2 | 4 is popped; visited, skipped | empty |
The program prints two lines: 0 2 1 and 3 4. In the transpose the adjacency list of 3 is [2, 4]; the edge 2 → 3 has become 3 → 2. This edge would join 3 to the previous component, but since 2 is visited, the DFS does not go there. Because 0 finished last in the first pass, the second pass started from {0, 1, 2}, a source component. This component has an edge to {3, 4} in the original graph; since that edge turns inward in the transpose, dfs2(0) cannot reach 3.
On the eight-vertex example Kosaraju's algorithm finds the same four components. The finishing order of the first pass is 3, 2, 1, 7, 6, 5, 4, 8. In the second pass the components are found in the order {8}, {4, 5}, {6, 7}, {1, 2, 3}. This order is exactly the reverse of Tarjan's: Kosaraju gives the components in topological order, Tarjan in reverse topological order.
| Tarjan | Kosaraju | |
|---|---|---|
| Number of DFS passes | 1 | 2 (one on the transpose) |
| Extra structures | index and low arrays, stack | transpose graph (O(V + E) memory), stack |
| Time | O(V + E) | O(V + E) |
| Order of components | Reverse topological | Topological |
The two algorithms have the same order of growth. Tarjan traverses the graph once and needs no copy; in practice it is usually faster. Kosaraju's logic is easier to grasp and its correctness easier to justify. Building the transpose takes O(V + E) time and memory but does not change the order of growth.
5.6Applications of traversal
By themselves, DFS and BFS only walk through the vertices in some order. When a few lines are added to a traversal, many questions about the structure of a graph can be answered in the same O(V + E) time. This section treats the most common applications.
5.6.1Topological sorting
A topological sort of a directed acyclic graph (DAG) is an ordering of its vertices such that for every edge u → v, u comes before v.
Edges express prerequisites of the kind "this first, then that". Courses with prerequisites, the build order of a project, the order in which the cells of a spreadsheet are computed, and the scheduling of jobs on a construction site are all topological sorting problems. For example, if "Data Structures" must be taken after "Programming", the study plan must contain these two courses in that order.
A topological order exists only in a directed acyclic graph. If the graph had a cycle u → v → … → u, then u would have to come both before and after every vertex of the cycle. Conversely, every DAG has at least one topological order. Moreover, a topological order is often not unique: two vertices with no path between them can be written in either order.
The graph in Figure 5.20 was obtained from the directed graph of the DFS trace by removing the edge 2 → 0. That edge added a cycle to the graph; with the edge gone, the graph is acyclic. There are two classical methods for topological sorting: Kahn's algorithm, which is BFS-based, and the reverse finishing order of DFS. On this graph the two give different results, but both are valid:
| Method | Order |
|---|---|
| Kahn | 0 1 7 2 3 4 5 6 |
| DFS (reverse finishing) | 0 7 1 2 4 3 5 6 |
In both orders each of the nine edges goes from left to right. For the edges 4 → 6 and 5 → 6, for example, 6 comes last in both. Vertex 7 only has to come after 0; Kahn places it after 1, and DFS places it right behind 0.
5.6.2Kahn's algorithm and a code trace
The idea of Kahn's algorithm is to do, in turn, the jobs that have no prerequisites left. A vertex with in-degree 0 has no prerequisite; it can be written first. A written vertex and its edges are regarded as deleted from the graph. This deletion reduces the in-degree of some vertices to 0, and those can now be written too. Ready vertices wait in a queue.
void kahn() {
int[] indeg = new int[n];
for (int v = 0; v < n; v++)
for (int w : adj[v]) indeg[w]++;
Queue<Integer> queue = new LinkedList<>();
for (int v = 0; v < n; v++)
if (indeg[v] == 0) queue.add(v);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int w : adj[v])
if (--indeg[w] == 0) queue.add(w);
}
}- The first nested loop increases the in-degree of each edge's target by one. Since all adjacency lists are walked once, this part is O(V + E).
- The second loop puts all vertices with in-degree 0 into the queue.
- The main loop takes a vertex from the queue and writes it. For each outgoing edge the target's degree is decremented:
--indeg[w]. The edge itself is not deleted; only the counter is decremented. A target whose degree drops to 0 is added to the queue.
| Taken | Degrees decremented | indeg (after) | Queue (after) | Output |
|---|---|---|---|---|
| — | degrees are counted; 0 enters the queue | 0 1 2 1 1 1 2 1 | 0 | |
| 0 | 1 → 0, 2 → 1, 7 → 0 | 0 0 1 1 1 1 2 0 | 1, 7 | 0 |
| 1 | 2 → 0 | 0 0 0 1 1 1 2 0 | 7, 2 | 0 1 |
| 7 | no outgoing edges | same | 2 | 0 1 7 |
| 2 | 3 → 0, 4 → 0 | 0 0 0 0 0 1 2 0 | 3, 4 | 0 1 7 2 |
| 3 | 5 → 0 | 0 0 0 0 0 0 2 0 | 4, 5 | 0 1 7 2 3 |
| 4 | 6 → 1 | 0 0 0 0 0 0 1 0 | 5 | 0 1 7 2 3 4 |
| 5 | 6 → 0 | 0 0 0 0 0 0 0 0 | 6 | 0 1 7 2 3 4 5 |
| 6 | no outgoing edges | same | empty | 0 1 7 2 3 4 5 6 |
The output is 0 1 7 2 3 4 5 6. When 4 is removed, the degree of 6 only drops to 1: one of the two prerequisites of 6 (4) is complete and the other (5) is still pending. Vertex 6 enters the queue only after 5 has been removed. This is the essence of Kahn's algorithm: a vertex is not written before all its prerequisites have been written.
Kahn's algorithm is also a cycle test. If the graph has a cycle, none of the vertices on the cycle ever has its degree reduced to 0, because each waits for the previous vertex on the cycle. The queue empties before all vertices have been written. Hence, if fewer than V vertices are written, the graph has a cycle. If the edge 2 → 0 is put back into the example graph, 0 gets in-degree 1 and no vertex with in-degree 0 is left at the start. The queue starts empty, no vertex is written, and the algorithm reports the cycle.
The running time is O(V + E): each vertex enters and leaves the queue once, and each edge is counted once and decremented once. Another structure can be used in place of the queue. If, for example, ready vertices are kept in a priority queue, the ready vertex with the smallest number is chosen at each step. This yields the lexicographically smallest topological order; the time rises to O((V + E) log V).
5.6.3Topological sorting with DFS
In the DFS-based method, vertices are pushed onto a stack at the moment they finish. When the traversal ends, the order popped from the stack is a topological order. This is the same job as the first pass of Kosaraju's algorithm:
void dfsFinish(int v) {
visited[v] = true;
for (int w : adj[v])
if (!visited[w]) dfsFinish(w);
stack.push(v); /* push when done */
}The main program calls dfsFinish from every unvisited vertex, then empties the stack and writes the vertices. On the graph of Figure 5.20, dfsFinish(0) descends first to 1, then from there to 2, 3, 5, and 6. Vertex 6 has no outgoing edges; it finishes first. Then 5 and 3 finish. The next neighbor of 2 is 4; the neighbor of 4, 6, has already finished, and 4 finishes. Then 2, 1, 7, and 0 finish. The finishing order is 6, 5, 3, 4, 2, 1, 7, 0; the order popped from the stack is its reverse, 0 7 1 2 4 3 5 6.
If DFS is run on a directed acyclic graph, then for every edge u → v, v finishes before u. The reverse of the finishing order is therefore a topological order.
The edge u → v is examined while the adjacency list of u is being walked. At that moment v can be in one of three states. If v is white (undiscovered), DFS descends from u to it, and the call of v returns before that of u. If v is dark (finished), it has already finished before u. Vertex v cannot be yellow: if it were, v would be on the call stack, that is, an ancestor of u; the tree path from v to u and the edge u → v would form a cycle. Since the graph is acyclic, this is impossible. In every case v finishes before u, and in the reverse order u comes first. ∎
The step "cannot be yellow" in the proof also gives the cycle test: if during DFS an edge to a yellow vertex is found, the graph has a cycle and no topological order exists. The DFS method also runs in O(V + E) time. Kahn's method produces the order from the beginning to the end. Because it keeps ready jobs in a queue, it also suits parallel scheduling. The DFS method is obtained by adding a single line to existing DFS code.
5.6.4Connected components
The number of connected components of an undirected graph is found by counting how many times the traversal is started. A new DFS (or BFS) is started from every unvisited vertex; each start traverses one new component completely.
int countComponents() {
boolean[] visited = new boolean[n];
int count = 0;
for (int v = 0; v < n; v++)
if (!visited[v]) { /* new component */
dfs(v, visited);
count++;
}
return count;
}Because all starts share the same visited array, each vertex is visited only once and the total time is again O(V + E). On a graph with nine vertices and the edges 0–1, 1–2, 3–4, 5–6, 6–7, 7–5, the method returns 4: the components are {0, 1, 2}, {3, 4}, {5, 6, 7}, and the lone {8}. If a component number is written to the vertices visited in each start, the question "are two vertices in the same component?" can later be answered in O(1) time.
The same count does not give the number of components in a directed graph. In a directed graph the set visited by a DFS depends on the choice of the start vertex. Take a graph with six vertices and the edges 0→1, 2→0, 3→2, 5→4. If vertices are tried from 0 to 5, DFS is started five times: from 0 only 1 is reached, and 2, 3, 4, and 5 are started separately. If vertices are tried from 5 down to 0, two starts suffice: from 5 to 4, and from 3 to 2, 0, and 1. Yet this graph has 2 components if edge directions are ignored and 6 components in the sense of strongly connected components. In a directed graph the right tool is Tarjan's or Kosaraju's algorithm.
5.6.5The bipartiteness test
To test whether a graph is bipartite is to try to color its vertices with two colors so that adjacent vertices get different colors. BFS does this coloring naturally: the start gets one color, its neighbors the other, and their new neighbors the first color again. In other words, even layers get one color and odd layers the other.
A graph is bipartite if and only if it contains no cycle of odd length.
In a bipartite graph every edge changes color. A cycle returns to the vertex where it started, that is, to the color it started with; so the cycle has an even number of color changes, that is, an even number of edges. For the converse, take a connected graph with no odd cycle and use the BFS layers. If there were an edge between two vertices u and w in the same layer, the BFS tree paths from s to u and to w would have equal length from the common ancestor where they part. These two paths and the edge u–w together would form an odd cycle. Hence every edge joins two consecutive layers, and the even/odd layer coloring is valid. In a graph that is not connected the same reasoning is applied to each component separately. ∎
boolean isBipartite(int s) {
Arrays.fill(color, -1);
color[s] = 0; queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : adj[v])
if (color[w] == -1) {
color[w] = 1 - color[v];
queue.add(w);
} else if (color[w] == color[v])
return false; /* same color */
}
return true;
}color[v] == -1 marks an uncolored vertex. An uncolored neighbor is given the opposite color with 1 - color[v] and added to the queue; the color array here also does the job of the visited array. If a colored neighbor has the same color as v, the two endpoints of an edge have fallen into the same set, and the method returns false at once. If the queue empties without trouble, the coloring is valid and true is returned. The method tests only the component of s; for a whole graph it is restarted from every uncolored vertex.
The graph in the trace is undirected with six vertices: the edges are 0–1, 0–2, 1–3, 2–3, 3–4, 3–5, 4–5. The graph has the cycle 0–1–3–2 (four edges) and the triangle 3–4–5 (three edges).
| Taken (color) | Neighbors | color (after) | Queue (after) |
|---|---|---|---|
| — | 0 enters the queue with color 0 | 0 −1 −1 −1 −1 −1 | 0 |
| 0 (0) | 1, 2 uncolored → color 1 | 0 1 1 −1 −1 −1 | 1, 2 |
| 1 (1) | 0 has the opposite color; 3 → color 0 | 0 1 1 0 −1 −1 | 2, 3 |
| 2 (1) | 0 and 3 have the opposite color | same | 3 |
| 3 (0) | 1, 2 have the opposite color; 4, 5 → color 1 | 0 1 1 0 1 1 | 4, 5 |
| 4 (1) | 3 has the opposite color; 5 has the same color → false | 0 1 1 0 1 1 | 5 |
The cycle 0–1–3–2 has four edges and does not spoil the coloring: 0 and 3 get one color, 1 and 2 the other. The problem is in the triangle 3–4–5; a cycle of three edges cannot be colored with two colors. Had the edge 4–5 been deleted, the method would have returned true. Because the test is a BFS, it runs in O(V + E) time.
Is the graph with the edges A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G bipartite?
Solution: the BFS distances from A are A 0, B 1, C 1, D 2, E 2, F 3, G 4. The vertices at even distance are {A, D, E, G} and those at odd distance {B, C, F}. Each of the eight edges joins these two sets; for example, the edge C–D joins layers 1 and 2, and the edge E–F joins layers 2 and 3. No two neighbors lie in the same layer, so the graph is bipartite. The cycles of the graph are the four-edge A–B–D–C–A and C–D–F–E–C and the six-edge A–B–D–F–E–C–A; all have even length.
5.6.6Cycles, bridges, and articulation points
Cycle detection is done differently in the two kinds of graph. In an undirected graph, if DFS meets a visited neighbor that is not the parent of the current vertex, there is a cycle. The parent exception is necessary because an undirected edge is listed in both directions, and the edge from a child back to its parent is not a cycle. In a directed graph only an edge to a vertex on the call stack, that is, a yellow one, indicates a cycle; an edge to a finished vertex does not. In the DFS trace the edge 2 → 0 went to the yellow 0 and signaled a cycle; the edge 4 → 6 went to the finished 6 and did not.
In a connected undirected graph, an edge whose deletion splits the graph in two is a bridge, and a vertex whose deletion splits it is an articulation point. Bridges and articulation points in a network are the weak spots where a single failure can split it. Both are found in a single DFS with Tarjan's low-link idea. In an undirected graph, disc(v) is the discovery order of v, and low(w) is the smallest discovery value reachable from the subtree of w using a single back edge. For the edge v–w of the DFS tree (w the child):
- if low(w) > disc(v), then v–w is a bridge: there is no back edge from the subtree of w to v or to the ancestors of v, and when the edge is deleted the subtree breaks off.
- if low(w) ≥ disc(v), then v is an articulation point (the root excepted; for the root the condition is that it has two or more children). In this case the subtree can return at most to v; when v is deleted it again breaks off.
In the example graph with letters A–G the only bridge is F–G. Since the DFS order is A, B, D, C, E, F, G, the discovery values are A 1, B 2, D 3, C 4, E 5, F 6, G 7. G's only neighbor is F, so low(G) = 7 > disc(F) = 6 and F–G is a bridge. Every other edge lies on a cycle; for example, the edge E–F is part of the cycle C–D–F–E, and even if it is deleted one can still go from E to F through C and D. F is also an articulation point: if it is deleted, G is left alone.
5.6.7Iterative deepening and random walks
Iterative deepening DFS (IDDFS) performs a series of DFS runs with the depth limit raised through 0, 1, 2, …. In each round DFS goes no deeper than the limit. If the goal is first found in the round with limit d, the shallowest solution is at depth d. The method combines the low memory use of DFS with the guarantee of BFS that it finds the shallowest solution. At first sight, re-traversing the upper layers in every round looks wasteful. But the great majority of vertices are in the deepest layer. In a tree in which every vertex has 10 children, BFS visits 111,111 vertices down to depth 5. IDDFS makes 123,456 visits in total; the difference is only about eleven percent. The method is common in the huge implicit graphs searched by chess and puzzle solvers.
A random walk moves at each step to a randomly chosen neighbor of the current vertex. It is not a traversal, because there is no guarantee that it visits all vertices, but it is a cheap way of sampling very large networks. The PageRank of a web page rests on the probability that someone walking randomly for a long time on the web graph is at that page.
5.7Common mistakes
Forgetting the visited array. In a graph with cycles, without a visited array DFS recurses forever and BFS keeps an endless queue. This is the source of the misconception that "BFS does not work on graphs with cycles". With marking in place, both algorithms work without trouble on graphs with cycles.
Marking at removal in BFS. The same vertex is added to the queue from many neighbors. The result may stay correct, but the queue grows to O(E). The right way is to mark the vertex when adding it to the queue.
Expecting shortest paths from DFS. The path by which DFS first reaches a target is not a shortest path. In an unweighted graph BFS is needed, in a weighted graph Dijkstra's algorithm. BFS does not find shortest paths in a weighted graph either; it finds only the path with the fewest edges.
Assuming stack-based DFS has the same order as the recursive version. When neighbors are pushed in list order, the visit order reverses: on the directed example, stack-based DFS prints 0 7 2 … and recursive DFS prints 0 1 2 …. If the recursive order is wanted, the neighbors are pushed in reverse order.
Skipping the "on the stack?" test in Tarjan's algorithm. The update min(…, index(w)) is made only for a w on the stack; a w whose component has been found is ignored. Otherwise the roots are lost and some components are never popped.
Traversing a disconnected graph from a single source. A traversal from one source sees only the vertices reachable from it. To cover the whole graph the traversal is restarted from every unvisited vertex. For the same reason, when a path is built after BFS, parent[] must hold −1 for unreachable targets.
Overlooking the representation. The O(V + E) time of DFS and BFS is for the adjacency list. If the same code is written with an adjacency matrix, each vertex's row is scanned end to end and the time becomes O(V2). On a sparse graph this difference can be more than a hundredfold.
5.8Summary
- Graph: G = (V, E), vertices and the edges joining them. The main kinds are directed, undirected, weighted, bipartite, cyclic, and complete graphs and trees. A complete graph on n vertices has n(n − 1)/2 edges; in an undirected graph the degrees sum to 2E.
- Representation: the adjacency list needs O(V + E) memory, the adjacency matrix O(V2). Traversal takes O(V + E) time with lists and O(V2) with a matrix. For sparse graphs the list is preferred.
- Traversal: visit every reachable vertex exactly once. Because of cycles a visited array is essential. If the waiting list is a stack the result is DFS; if it is a queue, BFS.
- DFS: follows one branch to its end, then backs up. In the recursive version the call stack does the backing up. The visit order depends on the order of neighbors; the edges by which vertices are first reached form the DFS tree.
- Stack-based DFS: marks at pop time; a vertex can enter the stack more than once, and the stack can grow to O(E). If neighbors are pushed in list order, the order is the reverse of the recursive version. It removes the risk of
StackOverflowErroron deep graphs. - BFS: advances layer by layer with a queue; it marks a vertex when adding it to the queue. With the arrays
dist[]andparent[]it finds shortest paths in an unweighted graph; the path is built by following parents back from the target. It does not find shortest paths in a weighted graph. - Maze: open cells are vertices and adjacent open cells are edges. BFS tries all paths simultaneously, and the path it finds when it first reaches the exit is the shortest.
- Strongly connected component: a maximal set of mutually reachable vertices. The components partition the vertices into disjoint parts; the component graph is acyclic.
- Tarjan: the index is the discovery order; the low-link is the smallest index reachable from the subtree by reaching vertices on the stack. If low(v) = index(v), then v is a root, and the vertices popped from the stack down to v form a component. An edge to a vertex whose component has been found is ignored. The time is O(V + E); the components come out in reverse topological order.
- Kosaraju: first a DFS that records the finishing order on a stack, then a second DFS on the transpose in stack order. Each DFS of the second pass finds one component. The time is again O(V + E).
- Applications: topological order (Kahn or reverse finishing order; if fewer than V vertices are written, there is a cycle), number of connected components, the bipartiteness test by two-coloring with BFS, cycle detection, bridges and articulation points, iterative deepening.
5.9Key terms
- graph
- vertex
- edge
- directed graph
- weighted graph
- bipartite graph
- adjacency list
- adjacency matrix
- graph traversal
- depth-first search (DFS)
- breadth-first search (BFS)
- pseudocode
- backtracking
- back edge
- ancestor
- parent
- shortest path
- connected component
- strongly connected component (SCC)
- topological sort
5.10Test Yourself
An undirected graph has the edges 0–1, 0–4, 1–2, 1–4, 2–3, 3–4, 3–5; the adjacency lists are in increasing order. What do
dfs(0)andbfs(0)print? According to BFS, which is the shortest path from 0 to 5?Answer
The adjacency lists are 0: [1, 4], 1: [0, 2, 4], 2: [1, 3], 3: [2, 4, 5], 4: [0, 1, 3], 5: [3]. DFS goes from 0 down to 1, 2, 3; since the neighbor 2 of 3 is marked, it moves on to 4. All neighbors of 4 are marked, so DFS returns to 3 and visits 5:
0 1 2 3 4 5. BFS discovers 1 and 4 first, then 2 from 1, 3 from 4, and last 5 from 3:0 1 4 2 3 5. The distances are 0, 1, 2, 2, 1, 3. Vertex 3 is discovered by 4, not 2, because 4 leaves the queue before 2. Following the parents gives the shortest path 0–4–3–5 (3 edges).Take the directed graph with the edges 0→1, 0→2, 1→3, 2→3, 3→4, 2→4; the adjacency lists are filled in this edge order. What does
dfsStack(0)print, and how many pushes does it make? What does recursivedfs(0)print?Answer
adj[0] = [1, 2],adj[2] = [3, 4]. Stack-based DFS pops, after 0, the last pushed vertex 2; after 2 the last pushed 4, then 3 (the neighbor 4 of 3 is pushed but is marked), and last 1:0 2 4 3 1. The total number of pushes is 1 + E = 7. Recursive DFS prints0 1 3 4 2. If the stack version pushes neighbors in reverse order, it also prints0 1 3 4 2.An undirected graph on seven vertices has the edges 0–1, 0–2, 1–3, 2–3, 3–4, 5–6. After
bfsDist(0), what isdist[]? What dopath(parent, 0, 4)andpath(parent, 0, 6)return?Answer
dist = [0, 1, 1, 2, 3, −1, −1]; 5 and 6 are unreachable. Sinceparent[4] = 3,parent[3] = 1,parent[1] = 0,path(parent, 0, 4)returns[0, 1, 3, 4]. Sinceparent[6] = −1, the loop adds only 6; the first item of the list is not 0 and the method returnsnull. Hadparent[]not been filled with −1,parent[6] = 0would remain and the method would return the nonexistent path[0, 6].Take the directed graph with the edges 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 4→6 (
adj[2] = [0, 3],adj[4] = [5, 6]). Which lines doesscc(0)print? What is the finalindex/lowvalue of each vertex?Answer
Vertices 0, 1, 2, 3, 4, 5, 6 are discovered in order, with indices 1 to 7. The edge 2 → 0 lowers
low[2]to 1, and the edge 5 → 3 lowerslow[5]to 4. Vertex 6 has no outgoing edges and is the first root. Then 3 becomes a root, and last 0. The output is three lines:6,5 4 3,2 1 0. The final values are 0: 1/1, 1: 2/1, 2: 3/1, 3: 4/4, 4: 5/4, 5: 6/4, 6: 7/7.For the DAG 0→2, 1→2, 1→3, 2→4, 3→4, 4→5, 3→5, what order do Kahn's algorithm and reverse finishing order give? What does Kahn print if the edge 5→1 is added to the graph?
Answer
At the start 0 and 1 have in-degree 0. Kahn prints
0 1 2 3 4 5: after 0 the degree of 2 drops to 1, after 1 vertices 2 and 3 become ready, after 3 vertex 4, and after 4 vertex 5 become ready. In DFS the finishing order is 5, 4, 2, 0, 3, 1; its reverse is1 3 0 2 4 5. When 5→1 is added, 1 gets in-degree 1. The queue holds only 0; when 0 is written, the degree of 2 drops to 1 and the queue empties. Only0is written; since fewer than 6 vertices are written, the graph has a cycle (1 → 3 → 5 → 1).Are a ring on five vertices (0–1–2–3–4–0) and a ring on six vertices (0–1–2–3–4–5–0) bipartite? On which edge does
isBipartite(0)returnfalsefor the first one?Answer
The six-vertex ring is bipartite: the colors alternate 0, 1, 0, 1, 0, 1. The five-vertex ring is a cycle of odd length and is not bipartite. BFS colors 0 with color 0, 1 and 4 with color 1, and 2 and 3 with color 0. When 2 is taken from the queue, its neighbor 3 is also of color 0: the method returns
falseat the edge 2–3.BFS is run from 0 on the complete graph with five vertices. How many insertions into the queue does the correct version, which marks on insertion, make, and how many does the version that marks on removal make?
Answer
The correct version adds each vertex once: 5 insertions. In the version that marks on removal, when 0 is removed 1, 2, 3, 4 are added; when 1 is removed, the still unmarked 2, 3, 4 are added again; when 2 is removed, 3 and 4; when 3 is removed, 4. In all 1 + 4 + 3 + 2 + 1 = 11 insertions are made and the queue reaches 7 items. The visit order is still 0 1 2 3 4, but work and memory have been wasted.
In an undirected graph with V = 500 vertices and E = 2000 edges, what is the total number of items in the adjacency lists and the number of cells in the adjacency matrix? By what factor does the approximate work of BFS differ between the two representations?
Answer
The lists hold 2E = 4000 items, the matrix has V2 = 250,000 cells. BFS takes about V + 2E = 4500 steps with lists and V2 = 250,000 steps with the matrix; the ratio is about 56.
5.11Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 20: presents BFS and DFS with white–gray–black coloring, discovery and finishing times, edge classification, and correctness proofs; topological sorting and Kosaraju's algorithm are there as well.
- R. Sedgewick, K. Wayne, Algorithms (4th ed., 2011), Sections 4.1 and 4.2: explains traversal of undirected and directed graphs with Java code; contains worked examples for mazes, components, and the Kosaraju–Sharir algorithm.
- J. Kleinberg, É. Tardos, Algorithm Design (2006), Chapter 3: treats BFS layers, the bipartiteness test, and topological sorting in DAGs with short, readable proofs.
- R. E. Tarjan, "Depth-First Search and Linear Graph Algorithms" (1972): the original paper that showed DFS to be the basis of linear-time graph algorithms and introduced the low-link idea.
5.12References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 20: Elementary Graph Algorithms).
- A. B. Kahn, "Topological Sorting of Large Networks", Communications of the ACM 5(11), 1962.
- J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2006 (Chapter 3: Graphs).
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Sections 4.1–4.2).
- R. E. Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM Journal on Computing 1(2), 1972.
Related pages: Chapter 5 slides · © Sercan Külcü. All rights reserved.