Graph Traversal

In one sentence

A traversal visits every node that can be reached from a starting node. Depth-first search (DFS) follows one path as far as it can, then goes back and tries another branch. Breadth-first search (BFS) visits nodes level by level using a queue, so it reaches every node along a path with the fewest edges.

This page covers the lessons of 26 September (the ideas behind DFS and BFS), 3 October (recursion and the DFS code) and 10 October (the BFS code, and DFS with a stack). The pictures are the ones from our slides (downloads at the bottom of the page).

1. Depth-first search

DFS starts at one node and keeps moving to a new node for as long as it can. When the current node has no unvisited neighbour left, it goes back to the node it came from and tries the next branch there. Every node is visited only once.

Start at node 1 in this graph:

1. From 1, go to 2. From 2, go to 3 (1 is already visited). From 3, go to 5.

   

2. Node 5 has no unvisited neighbour (2 and 3 are done), so go back to 3, then to 2, then to 1. Node 1 still has an unvisited neighbour, 4, so visit it.

   

The visit order is 1, 2, 3, 5, 4. Node 4 is a direct neighbour of 1, but it comes last, because DFS first went deep through 2, 3 and 5. Which branch is tried first depends on the order of the neighbours in adj[u], so a different order of input edges can give a different (but still correct) visit order.

1.1 Recursion first

DFS is written as a recursive function: a function that calls itself. The example from class:

int fib(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return fib(n - 1) + fib(n - 2);
}

We usually write our helpers as lambdas inside solve(). A lambda cannot see its own name, so we pass it to itself as the first parameter, self:

    auto fib2 = [&](auto self, int n)-> int {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return self(self, n - 1) + self(self, n - 2);
    };

    cout << fib(5) << "\n";
    cout << fib2(fib2, 5) << "\n";

Both lines print 8. Inside the lambda we write self(self, ...); from outside we call fib2(fib2, 5).

A lambda without self that still seems to work

If the body of fib2 says fib(n - 1) + fib(n - 2) instead of self(self, ...), the program still compiles and still prints 8. It is not recursion: the lambda is calling the ordinary function fib written above it. Delete that function and it stops compiling. A lambda declared with auto can never call itself by its own name.

1.2 The code

Mark the current node as visited, then call DFS on every neighbour that has not been visited yet. With an adjacency list:

void dfs(int u) {
    if (vis[u] == 1) { return; }

    cout << u << " ";
    vis[u] = 1;

    // list
    for (auto v: adj_list[u]) {
        // do we visit this node before
        if (vis[v]) continue;
        // visit v
        dfs(v);
    }
}

Two places to stop. The code checks vis twice, and they are two different gates:

• if (vis[u] == 1) { return; } at the top stops after the call has been made: we enter dfs(u) and leave at once.
• if (vis[v]) continue; inside the loop stops before the call: we never enter dfs(v) at all.

Either gate alone keeps DFS correct. The one inside the loop is cheaper, because it saves a function call every time a neighbour was already visited.

With an adjacency matrix the idea is the same, but we have to try every v from 1 to n and first check that the edge exists:

    for (int v = 1; v <= n; v++) {
        // do we have an edge between u and v
        if (adj_matrix[u][v] == 0) continue;

        // do we visit this node before
        if (vis[v]) continue;

        // visit v
        dfs(v);
    }

That loop costs \(n\) steps for every node, so \(n^2\) in total, even when the graph has very few edges. With the list we only look at real neighbours.

As a lambda inside solve():

    auto dfs = [&](auto self, int u) -> void {
        vis[u] = 1;
        for (auto v: adj[u]) {
            if (vis[v]) continue;
            self(self, v);
        }
    };

    dfs(dfs, 1);

Run it on the graph above:

Input            Output
5 5              1 2 3 5 4
1 2
1 4
2 3
2 5
3 5

Why a lambda inside solve()? n and adj are created inside solve(). A function written above solve() cannot see them, so we would have to move them outside and still fill them in inside solve(). A lambda with [&] sits inside solve() and can use everything that is already there.

1.3 DFS with a stack

Recursion is not the only way. The recursive calls already behave like a stack (last in, first out): the newest call is the first one to finish. So we can keep our own stack of nodes instead:

    stack<int> st;
    st.push(1);
    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (vis[u]) { continue; }
        vis[u] = 1;
        for (auto v: adj[u]) {
            if (!vis[v]) st.push(v);
        }
    }

The newest node on the stack is taken first, so we keep moving away from the start before we come back to the older nodes. That is depth-first. A node can be pushed more than once before it is taken out, which is why vis[u] is checked right after the pop.

Compare it with the BFS loop in §2.2: the only real difference is stack instead of queue.

Which one do we use? Normally the recursive one. In the recursive version, when self(self, v) returns we are back at u and can use what v found. For example, to count the nodes below u:

            self(self, v);
            sz[u] += sz[v];

With the stack, once u is popped it is gone; the loop never comes back to it, so there is no place to write that second line.

1.4 DFS that gives back an answer

So far dfs only walked around. It can also give back a number: "the best thing I found in the part I walked through". We did this on 24 October with I · Rumor.

The problem in short. Vova wants everyone to know a rumour. Person \(i\) starts spreading it if Vova pays them \(c_i\) gold, and after that friends tell friends for free. What is the least gold he has to pay?

First turn it into a graph. People are nodes, every pair of friends is an edge. Once one person in a connected piece knows the rumour, the whole piece knows it. So for every piece we pay only its cheapest person, and add those up.

Sample 1: \(c = 2, 5, 3, 4, 8\) and friends 1–4, 4–5.

pieces:   {1, 4, 5}   {2}   {3}
cheapest:  c1 = 2     c2 = 5  c3 = 3      answer 2 + 5 + 3 = 10

The DFS. dfs(u) returns the smallest \(c\) in the part it walks through. It starts with its own c[u], and every time a neighbour's call comes back, it keeps the smaller one:

    auto dfs = [&](auto self, int u)->ll {
        vis[u] = true;
        ll mn = c[u];
        for (int v : adj[u]) {
            if (vis[v]) {
                continue;
            }
            mn = min(mn, self(self, v));
        }
        return mn;
    };

There is only one return, after the loop. If u has no unvisited neighbours, the loop does nothing and we return c[u] itself.

Follow it on sample 1, starting at 1:

• dfs(1): mn = 2. Neighbour 4 is new, so call dfs(4).
  • dfs(4): mn = 4. Neighbour 1 is visited, skip. Neighbour 5 is new, call dfs(5).
    • dfs(5): mn = 8. Its only neighbour 4 is visited. Return 8.
  • back in dfs(4): mn = min(4, 8) = 4. Return 4.
• back in dfs(1): mn = min(2, 4) = 2. Return 2.

Then the loop in solve() starts a new DFS from every person who is still not visited; each start is a new piece:

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ans += dfs(dfs, i);
        }
    }

dfs(dfs, 2) returns 5 and dfs(dfs, 3) returns 3, so ans = 2 + 5 + 3 = 10. Use long long: up to \(10^5\) people with \(c_i\) up to \(10^9\).

BFS works too: pop a node, keep mn = min(mn, c[u]), and return mn when the queue is empty. Rumor can also be solved without any walking at all, with DSU.

The same three steps for every problem in this set

1. What are the nodes? What are the edges?
2. Draw the sample as a graph.
3. Say what the question asks in graph words ("the cheapest node in each piece"), then pick DFS or BFS.

2. Breadth-first search

BFS visits the nodes in increasing order of distance from the start: first the start itself, then every node 1 edge away, then every node 2 edges away, and so on. Nodes at the same distance can be visited in any order.

Start at node 1 in this graph:

Level	Nodes	Picture
distance 1	2, 4
distance 2	3, 5
distance 3	6

2.1 The queue

BFS keeps a queue (first in, first out). Take the node at the front. Every neighbour that has not been visited yet is marked as visited, given "my distance + 1", and pushed to the back.

Take out	Newly found (distance)	Queue afterwards
—	1 (0)	1
1	2 (1), 4 (1)	2, 4
2	3 (2), 5 (2)	4, 3, 5
4	— (1 is already visited)	3, 5
3	6 (3)	5, 6
5	— (6 is already visited)	6
6	—	empty

Final distances:

node	1	2	3	4	5	6
distance	0	1	2	1	2	3

Look at node 6: it can be reached through 3 or through 5, both in 3 edges. It is marked the first time it is seen and never pushed again. That is why we mark a node when we push it, not when we take it out: otherwise the same node could sit in the queue twice.

2.2 The code

The task from class: given a graph and a start node s, find the smallest number of edges from s to every other node.

DFS is a bad tool for this. On the graph of §1 it reaches node 5 along 1 → 2 → 3 → 5, which is 3 edges, although 1 → 2 → 5 is only 2. It would have to come back and fix distances again and again. BFS goes level by level, so the first time it sees a node is already along a shortest path.

dist[i] is the shortest distance from s to i. Before we start, every node is "not reached yet", written as INT_MAX (the largest int), and the start is 0 steps from itself:

    vector<int> dist(n + 1, INT_MAX);
    // dist[i] the shortest dist from s to i
    // dist[i] = INT_MAX init

    dist[s] = 0;

Then the queue loop:

    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); //get
        q.pop(); //delete
        for (auto v: adj[u]) {
            // if (dist[v] > dist[u] + 1) {
            if (dist[v] == INT_MAX) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

• There is no recursion, only a while loop that runs until the queue is empty.
• Taking a node out is two steps: q.front() reads the front, q.pop() deletes it. In C++ pop() gives nothing back (in Python it does).
• There is no vis array. dist does both jobs: a node whose distance is still INT_MAX has not been visited.

Reading dist[v] > dist[u] + 1. This was the first version of the check, now the commented line. dist[v] is the best distance we know for v so far. dist[u] + 1 is a new offer: go to u the shortest way, then take one more edge to v. If the old value is bigger than the offer, the offer is better, so we take it.

Follow node 5 on the graph of §1, starting from 1:

We are at	dist[u]	Offer for 5	dist[5] before	What happens
2	1	2	INT_MAX	INT_MAX > 2, so dist[5] = 2 and 5 is pushed
3	2	3	2	2 > 3 is false, nothing changes

Why > and not >=? The second example from class has 5 nodes and the edges 1–2, 1–3, 2–4, 3–4, 3–5, 4–5, starting from 1. Nodes 2 and 3 are both at distance 1, and both are neighbours of 4. At node 2 we set dist[4] = 2 and push 4. At node 3 the offer for 4 is 2 again. With >= we would write the same 2 a second time and push 4 a second time, for nothing.

The shorter check. Because BFS goes level by level, the first distance a node gets is already its shortest, so every node needs to be updated only once. A node that has been updated is no longer INT_MAX. So the check can simply be dist[v] == INT_MAX, and that is the line we kept.

Queries. When the loop is done, dist holds the answer for every node. Each question "how far is node d?" is one line, with no new search:

        cin >> d;
        cout << dist[d] << endl;

A run on the graph of §1 (one test case, then the edges, then the start, then 5 queries):

Input            Output
1                0
5 5              1
1 2              2
1 4              1
2 3              2
2 5
3 5
1
5
1 2 3 4 5

2.3 Watching the queue

In class we followed the queue on a tree, starting from node 15. The neighbours of 15 are 3, 8, 7, 6, 20, and the other neighbours of 3 are 1, 11, 10.

u	Queue after the pop	Pushed	Queue afterwards
—	—	15	15
15	empty	3, 8, 7, 6, 20	3, 8, 7, 6, 20
3	8, 7, 6, 20	1, 11, 10	8, 7, 6, 20, 1, 11, 10

The queue grows for a while, but every turn of the loop removes one node and no node is pushed twice, so it becomes empty in the end.

When u = 3, node 15 is a neighbour of 3 too. It is not pushed again, because dist[15] is 0, not INT_MAX. After these steps dist is 1 for 3, 8, 7, 6, 20 and 2 for 1, 11, 10: everything at distance 1 is in front of everything at distance 2.

2.4 When the problem does not say "graph"

On 31 October we looked at J · Two Buttons. You start with the number \(n\). One button doubles it, the other subtracts 1. What is the smallest number of presses to get \(m\)?

No graph is given, but we can ask the two questions from the start of this page: what are the nodes (the things), and what are the edges (the relationships)?

• Every number is a node.
• There is an edge from \(x\) to \(2x\) and an edge from \(x\) to \(x - 1\), because one press takes you there.
• The edges have a direction. From 4 you can go to 3, but one press does not take you from 3 back to 4.

"The smallest number of presses" now means "the shortest distance from \(n\) to \(m\)", and that is what BFS finds. Take \(n = 4\), \(m = 6\):

Presses	Numbers we can be at for the first time
0	4
1	8, 3
2	16, 7, 6, 2

6 appears at level 2, so the answer is 2, along 4 → 3 → 6.

How many nodes? \(m\) is at most \(10^4\), but sometimes the shortest way goes above \(m\) first, so it is not enough to stop at \(m\). Going past \(2 \cdot 10^4\) is never useful: you would spend presses making the number big, then even more presses bringing it back down. So nodes 1 to \(2 \cdot 10^4\) are enough.

2.5 Directed graphs and vis

To store a directed edge from u to v, do only one push_back:

adj[u].push_back(v);

For an undirected edge we do two, one for each direction. BFS itself does not change at all.

Can we drop vis on a directed graph? No. A direction does not stop you from walking in a circle. The graph 1 → 2, 2 → 3, 3 → 1 is directed, and without vis you would go round it forever. You can only drop it when the graph is directed and has no cycle at all. Such a graph is called a DAG (directed acyclic graph).

The magic lift from class is a good example. A building has floors 0 to \(m\), and from floor \(i\) the lift goes to floor \(i + 3\) or to floor \(i / 2\) rounded down. It is the same idea as Two Buttons: every floor is a node, and every button is a directed edge. Its edges do go in a circle, 1 → 4 → 2 → 1, so here we need the check. If dist[t] is still INT_MAX at the end, BFS never reached floor \(t\), so the answer is \(-1\).

3. DFS or BFS?

	DFS	BFS
order	one path as deep as possible, then back up	level by level
tool	recursion, or your own stack (§1.3)	a queue
gives distances?	no	yes, in number of edges
cost	\(O(n + m)\)	\(O(n + m)\)

Both look at every node once and every edge a constant number of times, so both are \(O(n + m)\) with an adjacency list.

4. Practice

Problem set 8.

This week (after 31 October): two problems, both with BFS. Try to submit them before Thursday. Read the problem and think for at most 25 minutes. No idea by then? Skip it, or send a message.

Problem	Idea
J · Two Buttons	write it again with BFS: every number is a node, and from \(x\) you can go to \(x \cdot 2\) and to \(x - 1\); the answer is the distance from \(n\) to \(m\) (§2.4)
K · Magic Lift	every floor is a node, and every button is a directed edge; print \(-1\) if the floor cannot be reached (§2.5)

From 10 October: template problems. Each one is the code from class with a small change.

Problem	Idea
H · Network Topology	no DFS or BFS: count the degree of every node, then look at how many nodes have degree 1, degree 2 and degree \(n - 1\)
I · Rumor	friends tell each other for free, so one payment covers a whole connected component; use DFS to find the cheapest person in each component (§1.4)

Earlier problems, if you want more:

Problem	Idea
E · Love Triangle	every plane likes exactly one other plane, so every node has one outgoing arrow; a love triangle is a cycle of length 3
G · Party	follow the managers upwards; people on one chain must be in different groups
F · New Year Transportation	start at cell 1 and keep taking the portal; do you land exactly on cell \(t\)?
A · Badge	draw an arrow from \(i\) to \(p_i\) and follow the arrows until you step on a student twice
B · Forever Winter	count the degree of every node
C · Ice Skating	two drifts in the same row or column are joined; use DFS to count the components
D · Quiz	we went through all 20 answers in class, submit them

5. Slides

• Graph Traversal (chapter 12), .pptx
• Basics of Graphs (chapter 11), .pptx

---

Credits & licenses

• All figures and the two examples are from our slides Graph Traversal; the explanations and tables are ours.
• The code in §1.1 and §1.2 is from the lesson of 3 October, unchanged. The matrix loop was written as a comment in class.
• The code in §1.3 and §2.2 is from the lesson of 10 October, unchanged. The second example in §2.2 was drawn in a graph editor in class.
• §1.4 follows the lesson of 24 October; its code is our reference solution for Rumor.
• §2.4 and §2.5 follow the lesson of 31 October.