Graphs and Traversals

What a graph is

Look at a metro map: the stations are dots, and the lines between them are connections. That is a graph. The stations are the vertices, the connections are the edges. A friend network is a graph too: people are vertices, friendships are edges.

A graph G = (V, E) is a set of vertices (nodes) V and a set of edges E, each edge joining two vertices. Trees, which you met in the BST and AVL chapters, are a special case: a connected graph with no cycles. Graphs drop both restrictions, so they can model road maps, course prerequisites, social networks, web links and task schedules.

This chapter uses one small undirected graph, G, in many examples. It has 7 vertices and 7 edges: 0–1, 0–2, 1–3, 2–4, 3–4, 3–5, 4–6.

          0
         / \
        1   2
        |   |
        3---4
        |   |
        5   6

Term	Meaning
undirected edge u–v	can be followed both ways (a friendship)
directed edge u → v	one way only (a hyperlink, "u must come before v")
adjacent / neighbour	v is a neighbour of u if the edge u–v (or u → v) exists
degree	number of edges touching a vertex; in a digraph, in-degree and out-degree
path	a sequence of vertices, each joined to the next by an edge; its length is the number of edges
cycle	a path with at least one edge that starts and ends at the same vertex, repeating no edge
connected	undirected graph in which every vertex can reach every other
connected component	a maximal connected piece of an undirected graph
DAG	directed acyclic graph: directed, with no directed cycle
sparse / dense	E close to V / E close to V²

In G: the neighbours of 3 are 1, 4 and 5, so deg(3) = 3. The path 0, 1, 3, 5 has length 3. The path 0, 1, 3, 4, 2, 0 is a cycle of length 5. G is connected.

Two counting facts come up constantly. In an undirected graph every edge adds 1 to the degree of each of its two ends, so the degrees add up to 2E (the handshake lemma). A simple undirected graph (no loops, no parallel edges) has at most V(V − 1)/2 edges; a simple directed graph at most V(V − 1).

Check it on G: the degrees are 2, 2, 2, 3, 3, 1, 1, which add up to 14 = 2 · 7 edges.

We number vertices 0 … V − 1 so that they can index arrays.

Representing a graph

In plain words: you can write a graph down in three ways. An edge list is a simple list of pairs, like a list of flights. An adjacency matrix is a big table with a tick for every pair that is connected, like the distance table at the back of a road atlas. Adjacency lists give each vertex its own contact list of neighbours, like the contacts on each person's phone.

Three standard representations, shown for the undirected edges 0–1, 0–2, 1–2, 2–3:

  0 --- 1          edge list:  (0,1) (0,2) (1,2) (2,3)
   \   /
    \ /            matrix:      0 1 2 3      lists:  0: 1, 2
     2                       0 [0 1 1 0]             1: 0, 2
     |                       1 [1 0 1 0]             2: 0, 1, 3
     3                       2 [1 1 0 1]             3: 2
                             3 [0 0 1 0]

// 1. Edge list: just the pairs
int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};

// 2. Adjacency matrix: matrix[u][v] is true when the edge exists
boolean[][] matrix = new boolean[4][4];
for (int[] e : edges) {
    matrix[e[0]][e[1]] = true;
    matrix[e[1]][e[0]] = true;       // undirected: store both directions
}

// 3. Adjacency lists: one list of neighbours per vertex
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 4; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);
    adj.get(e[1]).add(e[0]);         // leave this line out for a directed graph
}

	Edge list	Adjacency matrix	Adjacency lists
space	Θ(E)	Θ(V²)	Θ(V + E)
is there an edge u–v?	O(E)	O(1)	O(deg u)
visit all neighbours of u	O(E)	O(V)	O(deg u)
visit every edge	O(E)	O(V²)	O(V + E)
add an edge	O(1)	O(1)	O(1)
best for	Kruskal (sort the edges), input files	dense graphs, frequent edge tests	sparse graphs — most real graphs

A road network or a social network is sparse: a million vertices with a few hundred neighbours each. A matrix would need 10¹² cells; adjacency lists need space proportional to the number of edges actually present. Unless the graph is dense or you mostly ask "is u joined to v?", use adjacency lists.

For the graph G, the adjacency lists (sorted, as used in all traces below) are:

0: 1, 2
1: 0, 3
2: 0, 4
3: 1, 4, 5
4: 2, 3, 6
5: 3
6: 4

Breadth-first search (BFS)

BFS explores the graph in layers: first the start vertex s, then all vertices one edge away, then all vertices two edges away, and so on. A FIFO queue makes this happen, and a dist array doubles as the visited set.

static int[] bfs(List<List<Integer>> adj, int s, int[] parent) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);                 // -1 = not yet discovered
    Arrays.fill(parent, -1);
    Deque<Integer> queue = new ArrayDeque<>();
    dist[s] = 0;
    queue.add(s);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {           // mark when ENQUEUED, not when dequeued
                dist[v] = dist[u] + 1;
                parent[v] = u;
                queue.add(v);
            }
        }
    }
    return dist;
}

Worked example — BFS on G from 0, neighbours in increasing order. The queue is written front first; a vertex is "visited" as soon as it gets a dist value.

Step	Dequeue	Newly discovered	Queue after	Visited after	dist[0..6]
start	—	0	[0]	{0}	0 − − − − − −
1	0	1, 2	[1, 2]	{0, 1, 2}	0 1 1 − − − −
2	1	3 (0 is already visited)	[2, 3]	{0, 1, 2, 3}	0 1 1 2 − − −
3	2	4	[3, 4]	{0 … 4}	0 1 1 2 2 − −
4	3	5 (1 and 4 already visited)	[4, 5]	{0 … 5}	0 1 1 2 2 3 −
5	4	6	[5, 6]	{0 … 6}	0 1 1 2 2 3 3
6	5	—	[6]	{0 … 6}	unchanged
7	6	—	[]	{0 … 6}	unchanged

Visiting order: 0, 1, 2, 3, 4, 5, 6. The layers are {0}, {1, 2}, {3, 4}, {5, 6} — the "ripples":

layer 0:   0
layer 1:   1   2
layer 2:   3   4
layer 3:   5   6

Because the queue holds all vertices at distance k before any at distance k + 1, the first time BFS discovers v it has found a path with the fewest possible edges. So dist[v] is the shortest-path length in an unweighted graph, and parent[v] records the vertex it was discovered from. The parent pointers form a BFS tree. To rebuild the path to t, follow parents back to s and reverse:

Deque<Integer> path = new ArrayDeque<>();
for (int v = t; v != -1; v = parent[v]) path.push(v);   // push = add at the front
// path now reads s, ..., t

In the example, parent = [−1, 0, 0, 1, 2, 3, 4]. The path to 6: 6 → parent 4 → parent 2 → parent 0, so the path is 0, 2, 4, 6 (length 3 = dist[6]).

If dist[t] is still −1, t is not reachable from s.

Depth-first search (DFS)

DFS goes as deep as it can along one path and backtracks only when it is stuck. The natural code is recursive: the call stack remembers where to come back to.

static void dfs(List<List<Integer>> adj, int u, boolean[] visited) {
    visited[u] = true;
    System.out.print(u + " ");            // preorder: when u is first reached
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(adj, v, visited);
    }
}

Worked example — recursive DFS on G from 0, neighbours in increasing order. Indentation shows the call stack: each deeper line is a call made from the line above it.

dfs(0)            visited {0}               neighbours 1, 2
  dfs(1)          visited {0,1}             0 visited; go to 3
    dfs(3)        visited {0,1,3}           1 visited; go to 4
      dfs(4)      visited {0,1,3,4}         go to 2
        dfs(2)    visited {0,1,2,3,4}       0 and 4 visited → dead end, return
      (back in 4) 3 visited; go to 6
        dfs(6)    visited {0,1,2,3,4,6}     4 visited → return
      return from 4
    (back in 3)   go to 5
      dfs(5)      visited {0,…,6}           3 visited → return
    return from 3
  return from 1
  (back in 0)     2 already visited
return from 0

Visiting order: 0, 1, 3, 4, 2, 6, 5. Compare with BFS (0, 1, 2, 3, 4, 5, 6): DFS reaches 2 only after going deep through 1, 3 and 4.

The call stack at its deepest moment (while inside dfs(2)) is:

top →  dfs(2)
       dfs(4)
       dfs(3)
       dfs(1)
       dfs(0)

On a long path-shaped graph the recursion can be V levels deep and overflow the stack, so you may write DFS with an explicit Deque used as a stack:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(s);
while (!stack.isEmpty()) {
    int u = stack.pop();
    if (visited[u]) continue;             // a vertex can be pushed more than once
    visited[u] = true;
    System.out.print(u + " ");
    for (int v : adj.get(u)) {
        if (!visited[v]) stack.push(v);
    }
}

This version is also depth-first, but it does not produce the same order as the recursive one: the neighbour pushed last is popped first, so with lists in increasing order it explores the largest neighbour first. Push the neighbours in decreasing order if you need to reproduce the recursive order.

Worked example — the stack version on G from 0, lists in increasing order (the stack is written top first):

Step	Pop	Action	Push	Stack after (top first)
start			0	[0]
1	0	visit 0	1, 2	[2, 1]
2	2	visit 2	4	[4, 1]
3	4	visit 4	3, 6	[6, 3, 1]
4	6	visit 6	—	[3, 1]
5	3	visit 3	1, 5	[5, 1, 1]
6	5	visit 5	—	[1, 1]
7	1	visit 1	—	[1]
8	1	already visited: skip	—	[]

Visiting order: 0, 2, 4, 6, 3, 5, 1 — different from the recursive 0, 1, 3, 4, 2, 6, 5, but still depth-first (it goes 0 → 2 → 4 → 6 before backing up). Notice that 1 was pushed twice (steps 1 and 5); that is why the if (visited[u]) continue; line is needed. If you push the neighbours in decreasing order instead, the stack version prints 0, 1, 3, 4, 2, 6, 5 — the same as the recursive version.

	BFS	DFS
container	queue (FIFO)	stack (LIFO) or recursion
explores	layer by layer	one branch to the end, then backtracks
gives	shortest paths by edge count, levels	cycle detection, topological order, components
time on adjacency lists	O(V + E)	O(V + E)

Connected components

In plain words: a component is an island. From anywhere on an island you can walk to anywhere else on it, but not to another island. To count the islands, land on an island you have not visited yet, explore all of it, and repeat.

One traversal from s visits exactly the component containing s. To find every component, start a new traversal from each vertex that is still unvisited; the number of starts is the number of components.

int components = 0;
boolean[] visited = new boolean[n];
for (int s = 0; s < n; s++) {
    if (!visited[s]) {
        components++;
        dfs(adj, s, visited);             // marks the whole component
    }
}

Worked example — 6 vertices, edges 0–1, 1–2, 3–4 (vertex 5 has no edges):

  0---1---2       3---4       5

s	Visited before?	Action	Component	Visited after
0	no	components = 1, DFS from 0	{0, 1, 2}	{0, 1, 2}
1, 2	yes	skip
3	no	components = 2, DFS from 3	{3, 4}	{0 … 4}
4	yes	skip
5	no	components = 3, DFS from 5	{5}	{0 … 5}

Result: 3 components.

An isolated vertex (degree 0) is a component on its own. The whole loop is still O(V + E): every vertex is marked once and every list is scanned once.

Cycle detection

In plain words: you are walking through a maze and you arrive at a place you have already visited — without simply turning round and going back the way you came. Then there must be a loop.

Undirected graphs. During a DFS, meeting an already-visited neighbour means a cycle — except for the vertex you just came from, because the edge u–v is stored in both lists. Pass the parent along and ignore it:

static boolean hasCycle(List<List<Integer>> adj, int u, int parent, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            if (hasCycle(adj, v, u, visited)) return true;
        } else if (v != parent) {
            return true;                  // visited, and not the edge we came in on
        }
    }
    return false;
}

Worked example — hasCycle(adj, 0, -1, visited) on G:

Call	Came from	What happens
visit 0	−1	neighbour 1 is new → go
visit 1	0	neighbour 0 is visited but it is the parent → ignore; 3 is new → go
visit 3	1	1 is the parent → ignore; 4 is new → go
visit 4	3	2 is new → go
visit 2	4	neighbour 0 is visited and is not the parent (4) → cycle!

The cycle found is 0 – 1 – 3 – 4 – 2 – 0. On a tree, for example 0–1, 1–2, 1–3, every visited neighbour is the parent, so hasCycle returns false.

Directed graphs. Here "already visited" is not enough: in 0 → 1, 0 → 2, 2 → 1 the vertex 1 is reached twice, yet there is no cycle. Give each vertex one of three colours:

• WHITE — not reached yet;
• GREY — on the current recursion stack (its call has started but not finished);
• BLACK — finished: everything reachable from it has been explored.

An edge u → v with v GREY points back to an ancestor on the current path: that is a back edge, and it closes a directed cycle. An edge to a BLACK vertex is harmless.

Think of GREY as "the rooms on the corridor I am walking along right now" and BLACK as "rooms I have completely explored and left". Arriving again at a room on your current corridor means you walked in a circle. Arriving at a room you already finished only means two corridors lead to the same place.

static final int WHITE = 0, GREY = 1, BLACK = 2;

static boolean cyclic(List<List<Integer>> adj, int u, int[] colour) {
    colour[u] = GREY;
    for (int v : adj.get(u)) {
        if (colour[v] == GREY) return true;              // back edge
        if (colour[v] == WHITE && cyclic(adj, v, colour)) return true;
    }
    colour[u] = BLACK;
    return false;
}

Worked example 1 — edges 0 → 1, 0 → 2, 2 → 1 (no cycle). Colours of vertices 0, 1, 2 (W = white, G = grey, B = black):

Event	Colours 0 1 2
enter 0	G W W
enter 1 (from 0)	G G W
finish 1 (no out-edges)	G B W
enter 2 (from 0)	G B G
edge 2 → 1: 1 is BLACK → harmless	G B G
finish 2	G B B
finish 0	B B B → no cycle

Worked example 2 — edges 0 → 1, 1 → 2, 2 → 3, 3 → 1 (cycle 1 → 2 → 3 → 1):

Event	Colours 0 1 2 3
enter 0	G W W W
enter 1	G G W W
enter 2	G G G W
enter 3	G G G G
edge 3 → 1: 1 is GREY → back edge → cycle!

Bipartite graphs and 2-colouring

In plain words: can you split everybody into two teams so that every edge joins people from different teams? For example, students on one side and courses on the other: every "is enrolled in" edge goes from a student to a course. Test it by colouring: give the start vertex red, all its neighbours blue, their neighbours red, and so on. If you ever have to give two neighbours the same colour, it is impossible.

A graph is bipartite if its vertices can be split into two groups so that every edge joins the two groups (students and courses, workers and jobs). Test it by trying to 2-colour it with BFS: give the start colour 0, every neighbour the opposite colour, and fail as soon as an edge joins two vertices of the same colour. Repeat from every uncoloured vertex so that disconnected graphs are handled.

Worked example 1 — G, BFS from 0 (colour −1 = not coloured yet):

Dequeue	Colours of 0 … 6 afterwards	Note
0	0, 1, 1, −, −, −, −	1 and 2 get the opposite colour of 0
1	0, 1, 1, 0, −, −, −	3 gets the opposite of 1
2	0, 1, 1, 0, 0, −, −	4 gets the opposite of 2
3	—	edge 3–4: both have colour 0 → not bipartite

G is not bipartite because of its cycle 0 – 1 – 3 – 4 – 2 – 0, which has 5 edges (odd).

Worked example 2 — the square 0–1, 1–2, 2–3, 3–0 with a tail 2–4, 4–5:

  0---1
  |   |
  3---2---4---5

The BFS gives colours 0, 1, 0, 1, 1, 0 to vertices 0 … 5, and no edge joins equal colours. So the graph is bipartite with teams {0, 2, 5} and {1, 3, 4}.

A graph is bipartite if and only if it has no cycle of odd length. So every tree is bipartite, an even cycle is bipartite, and a triangle is not.

Topological sort

A topological order of a directed graph lists every vertex so that for each edge u → v, u comes before v — think "take CPS 2231 before CPS 2232". It exists exactly when the graph is a DAG, and a DAG usually has many valid orders.

The examples below use this prerequisite DAG with 6 courses (an edge u → v means "u before v"):

 0 Java I  ──▶  1 Java II  ──▶  3 Data Structures  ──▶  4 Algorithms
                   │                  ▲                     ▲
                   ▼                  │                     │
              5 Databases       2 Discrete Maths ───────────┘

 edges: 0→1, 1→3, 1→5, 2→3, 2→4, 3→4

Kahn's algorithm repeatedly removes a vertex with in-degree 0:

int[] inDegree = new int[n];
for (List<Integer> list : adj) for (int v : list) inDegree[v]++;
Deque<Integer> ready = new ArrayDeque<>();      // or a PriorityQueue for "smallest first"
for (int v = 0; v < n; v++) if (inDegree[v] == 0) ready.add(v);
List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
    int u = ready.poll();
    order.add(u);
    for (int v : adj.get(u)) {
        if (--inDegree[v] == 0) ready.add(v);    // all of v's prerequisites are done
    }
}
if (order.size() < n) System.out.println("cycle"); // the rest wait on each other forever

Worked example — Kahn with a FIFO queue, adjacency lists in increasing order:

Step	Take	In-degrees of 0 … 5 after	Ready queue after	Order so far
start		0, 1, 0, 2, 2, 1	[0, 2]
1	0	0, 0, 0, 2, 2, 1	[2, 1]	0
2	2	0, 0, 0, 1, 1, 1	[1]	0, 2
3	1	0, 0, 0, 0, 1, 0	[3, 5]	0, 2, 1
4	3	0, 0, 0, 0, 0, 0	[5, 4]	0, 2, 1, 3
5	5	unchanged	[4]	0, 2, 1, 3, 5
6	4	unchanged	[]	0, 2, 1, 3, 5, 4

Result: 0, 2, 1, 3, 5, 4. All 6 vertices came out, so the graph has no cycle. Check one rule: 3 → 4, and 3 is before 4. ✓

The container decides which valid order you get. A FIFO queue gives one order; a PriorityQueue<Integer> always takes the smallest available vertex and gives the lexicographically smallest order. If fewer than V vertices come out, the remaining vertices all have in-degree ≥ 1 among themselves, which is only possible if they contain a cycle.

With a PriorityQueue on the same DAG the choices are: {0, 2} → take 0; {1, 2} → take 1; {2, 5} → take 2; {3, 5} → take 3; {4, 5} → take 4; {5} → take 5. Result: 0, 1, 2, 3, 4, 5 — also valid, and the smallest possible.

And with a cycle: for 0 → 1, 1 → 2, 2 → 3, 3 → 1 the in-degrees are 0, 2, 1, 1. Kahn takes 0, which lowers in-degree(1) to 1, and then the ready queue is empty. Only 1 of 4 vertices came out, so there is a cycle (1 → 2 → 3 → 1).

DFS finishing order. Run DFS from every unvisited vertex and add each vertex to a list when its call finishes (postorder). A vertex finishes only after everything reachable from it has finished, so reversing the finishing order gives a topological order.

static void finish(List<List<Integer>> adj, int u, boolean[] visited, Deque<Integer> out) {
    visited[u] = true;
    for (int v : adj.get(u)) if (!visited[v]) finish(adj, v, visited, out);
    out.push(u);                          // push = prepend, so out is already reversed
}

Worked example — finish on the same DAG, starting from 0, 1, …, 5 in turn (skipping visited vertices):

start 0:  0 → 1 → 3 → 4      4 has no out-edges: finish 4     out = [4]
                             back in 3: finish 3               out = [3, 4]
          back in 1: go to 5, finish 5                         out = [5, 3, 4]
          finish 1                                             out = [1, 5, 3, 4]
          finish 0                                             out = [0, 1, 5, 3, 4]
start 2:  3 and 4 already visited: finish 2                    out = [2, 0, 1, 5, 3, 4]

Result: 2, 0, 1, 5, 3, 4 — a third valid order. The vertex that finishes first (4, Algorithms) is the one that comes last in the order.

(Combine it with the three colours if the input might contain a cycle.)

Cost: O(V + E)

In plain words: every algorithm in this chapter visits each vertex once and looks at each edge once (twice for undirected edges, once from each end). So the work is proportional to the size of the graph — you cannot do better, because you have to look at the whole graph at least once.

Every algorithm in this chapter marks each vertex once and scans each adjacency list once. The lists have total length E (directed) or 2E (undirected), so the total work is O(V + E), linear in the size of the graph. With an adjacency matrix the "scan the neighbours of u" step costs O(V) per vertex, so the same algorithms cost O(V²) — fine for dense graphs, wasteful for sparse ones.

Key takeaways

• A graph is vertices plus edges; store it as adjacency lists (Θ(V + E) space) unless it is dense or you mostly test single edges.
• BFS uses a queue and explores in layers; in an unweighted graph dist[v] is the fewest number of edges from s, and parent rebuilds the path. Mark vertices when they are enqueued.
• DFS uses recursion or a stack and goes deep first. The stack version with increasing lists visits the largest neighbour first; push in decreasing order to match the recursive order.
• Components: start a new traversal from every unvisited vertex and count the starts.
• Cycles: undirected → a visited neighbour that is not the parent; directed → an edge to a GREY vertex (three colours).
• Bipartite ⇔ 2-colourable ⇔ no odd cycle.
• Topological order exists only for a DAG: Kahn (remove in-degree-0 vertices) or reverse DFS finishing order. Many orders can be correct — follow the tie-breaking rule.
• All of these algorithms cost O(V + E) on adjacency lists.