• V = number of vertices, E = number of edges
• Edges may be directed (one-way) or undirected (both ways)
• Edges may carry weights; plain BFS and DFS ignore them
• Unlike a tree, a graph may contain cycles, so revisiting is possible and must be prevented
• Both traversals run in O(V + E) time and O(V) space

A graph is the most general way to describe "things and the connections between them", and almost every problem in this section is really a question about a graph wearing a disguise. So it is worth building the idea from nothing.

A graph is two sets. There are vertices — also called nodes, the things themselves — and edges, each of which joins a pair of vertices. That is the entire definition. Cities and roads, people and friendships, courses and prerequisites, web pages and links: all graphs.

Two properties change what algorithms apply, and you should establish both before writing code.

An edge is undirected if it can be crossed both ways, like a two-way road. It is directed if it only works one way, like a prerequisite or a one-way street. In a directed graph, an edge from A to B says nothing whatsoever about getting from B to A.

An edge is weighted if it carries a number — a distance, a cost, a delay. Plain traversal ignores weights entirely, which is why the weighted shortest-path algorithms later in this section are separate machinery rather than small variations.

A tree is a graph too, but a very well-behaved one: it is connected, and it has exactly one route between any two nodes. That means walking a tree can never bring you back somewhere you have already been. You can recurse into children freely and the recursion is guaranteed to end.

A general graph offers no such promise. Consider three nodes joined in a triangle. Starting at the first, you step to the second, then the third, then back to the first — and now you repeat the same loop forever. Nothing in the structure stops you.

This is the single difference that shapes every graph algorithm: a graph can contain cycles, so you must remember where you have been. That memory is a visited set — a hash set of node labels, or a boolean array when nodes are numbered 0 to V-1. Before entering a node you check whether it is recorded; if it is, you skip it. Remove the visited set from any traversal below and it runs forever on any graph containing a cycle.

The visited set also does a second, quieter job: it stops repeated work. Even in a graph with no cycles at all, several routes may lead to the same node, and without a record you would explore everything beyond it once per arriving route — correct, but exponentially slow.

The representation you choose caps the speed of everything built on top, so it is not a detail.

An adjacency list maps each node to a list of its neighbours. Node 0 might map to [1, 4], node 1 to [0, 2], and so on. Finding a node's neighbours is immediate, and the total storage is proportional to the number of edges actually present. This is the standard choice.

An adjacency matrix is a V × V table where entry (i, j) records whether an edge joins i and j. Checking one specific pair is instant, which is occasionally what you want, but listing a node's neighbours means scanning an entire row of V entries — including all the zeros. That pushes traversal to O(V²) and the storage to V² regardless of how sparse the graph is. It is worth using only when the graph is dense, or when the input arrives in that form, as it does in Number of Provinces.

An edge list is just a list of pairs. Compact, and the natural input format, but useless for traversal on its own, since finding one node's neighbours requires scanning every edge. Converting an edge list into an adjacency list is a standard first step:

from collections import defaultdict

adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)      # add the reverse ONLY if the graph is undirected

The first traversal order visits nodes by increasing distance from the start. Everything one edge away comes first, then everything two edges away, and so on.

The reason this works is worth stating carefully, because it is the property the whole next section depends on. A node first appears in the ring matching its true minimum number of edges from the start. It cannot appear earlier — that would mean a shorter route exists, contradiction. And it cannot appear later, because the moment any node at distance d is expanded, every unvisited neighbour of it is claimed for distance d+1. So the order of discovery is exactly the order of distance.

Holding the frontier requires a structure that returns nodes in the order they were added — a queue, first in, first out.

from collections import deque

def bfs(adj, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            if nxt not in visited:
                visited.add(nxt)        # mark on discovery, not on removal
                queue.append(nxt)
    return order

The other order plunges. From the current node, step to a neighbour, and from there to one of its neighbours, continuing until stuck; then back up one level and try the next untried branch.

Recursion expresses this naturally, because the language's call stack already does the backing-up for you.

def dfs(adj, start):
    visited = set()
    order = []

    def visit(node):
        visited.add(node)               # mark on entry, before recursing
        order.append(node)
        for nxt in adj[node]:
            if nxt not in visited:
                visit(nxt)

    visit(start)
    return order

Two things about the recursion deserve saying plainly. A recursive function needs a base case — here, a node whose neighbours are all visited simply makes no further calls and returns — and it needs progress, which the visited set provides: every call permanently removes one node from the unvisited pool, and that pool cannot shrink forever.

And when visit calls itself on a neighbour, do not try to trace where that call goes. Assume it visits everything reachable from there and returns. That is an induction argument, not hand-waving: the base case is correct by inspection, and if every call on a strictly smaller unvisited pool is correct, then a call that marks its own node and delegates its neighbours is correct too.

Mechanically, each call in progress holds a stack frame — its arguments and the point to resume at. Those frames are the memory cost, and on a graph shaped like a long chain the stack can reach V frames deep, which on a large graph will exceed the interpreter's limit. Swapping the call stack for one you manage fixes it with no change in behaviour:

def dfs_iterative(adj, start):
    visited = {start}
    stack = [start]
    while stack:
        node = stack.pop()              # pop, not popleft — that is the only change
        for nxt in adj[node]:
            if nxt not in visited:
                visited.add(nxt)
                stack.append(nxt)

Set that beside the BFS above. The code is identical except for which end of the container is drained. That single choice is the entire difference between the two traversals — a queue gives you distance ordering, a stack gives you depth-first descent.

Count it rather than asserting it. The visited set guarantees each node is entered exactly once, contributing V units of work. When a node is entered, its neighbour list is scanned once — and summing the lengths of every neighbour list over all nodes gives exactly E for a directed graph, or 2E for an undirected one, since each edge appears in two lists. So the total is proportional to V + E.

Both terms matter and neither dominates in general. A graph can have many nodes and almost no edges, or few nodes and nearly V² edges. Writing O(V + E) rather than O(E) is what acknowledges that isolated nodes still cost something to look at.

This is the decision to internalise, because both visit the same nodes at the same cost and the choice is purely about what the question asks.

Use BFS when the answer involves distance — shortest path, minimum number of steps, fewest moves, earliest time. Only BFS produces nodes in distance order, and only on an unweighted graph, where every edge counts the same. The moment edges carry different weights, the ring argument collapses, because a two-edge route may cost less than a one-edge route, and you need Dijkstra's algorithm instead.

Use DFS when the answer involves reachability or structure — is anything reachable, how many separate components exist, does a cycle exist, what ordering satisfies the dependencies. None of these care how far apart nodes are, so BFS's ordering guarantee buys nothing and its queue is pure overhead. DFS is also shorter to write and gives you something BFS does not: a natural notion of finishing a node, after all its descendants are done. Topological sorting and directed cycle detection are both built on that.

Memory splits the same way. DFS holds one route, so its cost is the longest path. BFS holds a whole ring, which on a wide graph can be a large fraction of all nodes at once. On a broad shallow graph DFS is far lighter; on a deep narrow one BFS avoids a stack overflow.

One traversal reaches only the component containing its start. If the problem concerns the whole graph, wrap it:

visited = set()
components = 0
for node in all_nodes:
    if node not in visited:
        components += 1
        visit(node)          # consumes this entire component

That outer loop is worth recognising as a pattern in its own right, because it appears constantly. The inner traversal consumes one component; the outer loop counts how many times it had to start over. Number of Provinces is precisely this, and so is counting islands in a grid.

Train the reflex: when a problem mentions things and relationships between them, name the vertices and name the edges before doing anything else. Then ask one question — does the answer depend on how far apart things are? If yes, BFS. If it depends only on what connects to what, DFS.