Graphs and trees: BFS and DFS for the algorithms exam

If you are taking Algorithms and Data Structures (computer science or engineering), lectures started a few weeks ago, and this is usually the period when, after complexity, graphs and trees arrive. The winter-session exam, in January or February, is eight to ten weeks away: you have time to build the method calmly. This topic has one advantage: hand traces can be learned, and in the exam they are almost always the surest way to pick up marks. Before this post it helps to be clear on complexity with big-O notation; for the in-memory representation with nodes and references you also need pointers in C.

Representing a graph

A graph $G=(V,E)$ has a set of nodes (vertices) $V$ and a set of edges $E$. We will also use $V$ and $E$ for their sizes, as in the costs. Two standard representations:

• Adjacency lists: for each node, the list of its neighbours. It takes $O(V+E)$ space and is the natural choice for sparse graphs.
• Adjacency matrix: a $V\times V$ table with 1 (or the weight) if the edge exists. It takes $O(V^2)$ and lets you find out in constant time whether two nodes are connected.

In an undirected graph each edge appears twice (in two lists, in two symmetric cells): the sum of the degrees is $2E$.

The graph used throughout the article has 6 nodes $A,\dots ,F$ and 6 edges: $A-B$, $A-C$, $B-D$, $C-D$, $C-E$, $E-F$. Adjacency lists, in alphabetical order:

The degrees are 2, 2, 3, 2, 2, 1: they add up to 12, that is $2E$ with $E=6$.

BFS: breadth-first traversal with a queue

You start from a source, mark it and put it in the queue. While the queue is not empty: take out the first node and put its not yet marked neighbours in the queue, marking them straight away.

BFS(G, s):
    mark s; queue = [s]
    while queue is not empty:
        u = dequeue(queue)
        visit u
        for each v in neighbours(u):
            if v is not marked:
                mark v; enqueue v

Trace from $A$:

1. Dequeue $A$: enqueue $B,C$. Queue: $[B,C]$.
2. Dequeue $B$: $A$ is marked, enqueue $D$. Queue: $[C,D]$.
3. Dequeue $C$: $A$ and $D$ already marked, enqueue $E$. Queue: $[D,E]$.
4. Dequeue $D$: neighbours $B,C$ are already marked. Queue: $[E]$.
5. Dequeue $E$: enqueue $F$. Queue: $[F]$.
6. Dequeue $F$. Queue empty.

BFS visiting order: $A,B,C,D,E,F$. The level at which I discover a node is its minimum distance in edges: $A=0$, $B=C=1$, $D=E=2$, $F=3$. That is why BFS finds shortest paths in unweighted graphs.

DFS: depth-first traversal with recursion

You move on to the first unvisited neighbour and go back only when the neighbours run out.

DFS(u):
    mark u; visit u
    for each v in neighbours(u):
        if v is not marked:
            DFS(v)

Trace from $A$: I start at $A$ and go to $B$; from $B$ the neighbour $A$ is marked, so I go to $D$; from $D$, $B$ is marked, I go to $C$; from $C$, $A$ and $D$ are marked, I go to $E$; from $E$ I go to $F$. From $F$ there is nothing else and I backtrack all the way to $A$.

DFS visiting order: $A,B,D,C,E,F$. Compared with BFS it changes: $D$ comes before $C$, because DFS goes deep before coming back. The stack of recursive calls does the job that the queue does in BFS. If you write DFS iteratively with an explicit stack, watch the order: if you push the neighbours in alphabetical order, the first one popped is the last, so the visiting order is reversed compared with the recursive one, unless you push them in reverse.

Complexity: O(V+E)

With adjacency lists, in both traversals each node is marked and processed once (cost $V$) and each list is scanned once; the lists hold $2E$ elements in all for an undirected graph, $E$ for a directed one. The cost is

With the adjacency matrix, to find the neighbours of a node you have to scan a whole row of $V$ cells: for $V$ nodes the cost becomes $O(V^2)$. On sparse graphs lists win.

Binary trees: pre-order, in-order and post-order

A tree is a connected graph with no cycles; a binary tree has, for each node, at most one left child and one right child. Traversals are a DFS with three variants, depending on when you visit the root:

• pre-order: root, left subtree, right subtree;
• in-order: left, root, right;
• post-order: left, right, root.

Take the tree with root 8, whose children are 3 and 10; the children of 3 are 1 and 6; the children of 6 are 4 and 7; 10 has only a right child 14, and 14 has only a left child 13.

• Pre-order: $8,3,1,6,4,7,10,14,13$
• In-order: $1,3,4,6,7,8,10,13,14$
• Post-order: $1,4,7,6,3,13,14,10,8$
• Level by level (BFS on the tree): $8,3,10,1,6,14,4,7,13$

In this tree the rules of the binary search tree hold (smaller values on the left, larger on the right), so the in-order traversal comes out sorted. It is an exam observation, but it holds only for that type of tree.

Typical mistakes in the exam

Order of the neighbours. The visiting order depends on the order in which the adjacency lists are written. If the question does not say, state it (“neighbours in alphabetical order”): with the lists reversed, on our graph BFS would give $A,C,B,E,D,F$ and DFS $A,C,E,F,D,B$. An answer different from the model solution can still be correct, provided you state the convention.

Already visited nodes. Forgetting the marking means going back to nodes already seen and, if there is a cycle, never terminating. Another variant: in BFS you mark the node when you dequeue it rather than when you enqueue it, and so you can put it in the queue several times.

Mixing up queue and stack. BFS with a stack is not BFS.

Pre-, in- and post-order. Write the sequence from the definition, starting at the root and descending recursively, not by intuition.

Cost. Saying $O(V^2)$ for lists, or $O(E)$ without the $V$: in a disconnected graph or one with isolated nodes you cannot drop the $V$ term.

Three worked exercises

1. Shortest path with BFS

What is the minimum number of edges to go from $A$ to $F$ in the graph above? Give a path.

From the BFS trace: $F$ is discovered from $E$ at level 3, $E$ from $C$ at level 2, $C$ from $A$ at level 1. Path $A\to C\to E\to F$, 3 edges. There is no shorter path: to reach $F$ you must go through $E$, the only neighbour of $F$, and $E$ can be reached only from $C$, which is at distance 1 from $A$.

2. Lists or matrix?

Compare the space for the 6-node, 6-edge graph and for a graph with 1000 nodes and 3000 edges.

For our graph the matrix has $6\cdot 6=36$ cells, the lists $2E=12$ elements (plus 6 heads). With $V=1000$ and $E=3000$: the matrix has $1,000,000$ cells, the lists about $6000$ elements (plus 1000 heads). The graph is very sparse, and indeed the lists cost a small fraction. For a traversal, the comparison is $O(V+E)=O(4000)$ against $O(V^2)=O(1,000,000)$.

3. Trees: rebuilding from a pair of traversals

Pre-order $A,B,D,E,C$; in-order $D,B,E,A,C$. Rebuild the tree and write the post-order.

The root is the first in the pre-order: $A$. In the in-order, $D,B,E$ are to the left of $A$ and $C$ to the right. The left subtree has pre-order $B,D,E$: root $B$; in the in-order $D$ is to the left of $B$ and $E$ to the right. So $A$ has as children $B$ (with children $D$ and $E$) and $C$. Post-order: $D,E,B,C,A$.

Test yourself

For graphs and trees the page of university practice tests is useful, as it collects questions by course: check how much of Algorithms it covers, because coverage depends on the course. The most useful exercise is still redoing the traces by hand on a graph of your own, changing the source and the order of the neighbours. Studying Karnaugh maps and Boolean algebra is another Fundamentals topic where tracing by hand pays off in the same way. More resources are on the computer science page; for a 1-to-1 online session on traces, you can start with a free introductory call.