Graphs: BFS, DFS, Connected Components and Topological Sort

Few problems say "graph". They say stops and tram links, cells of a map, guests who refuse to sit together, modules that must be built before others. Each of those is a set of things (vertices) and pairs of things that are related (edges). Once you see the graph, a small set of algorithms answers a surprising number of questions: the fewest steps from here to there, which things are connected, whether the things can be split into two compatible groups, and in what order to process them when some must come before others.

All of these are traversals: a systematic walk that visits every reachable vertex once and looks at every edge a constant number of times. That gives the bound that makes them so useful, O(V + E) for V vertices and E edges. With V and E up to a few hundred thousand, the complexity table says that is comfortably fast, and it is the best you can hope for, since reading the input already costs that much.

The usual failures are not about the idea. They are about details: an undirected edge stored in one direction only, a vertex marked visited at the wrong moment, a graph assumed to be connected when it is not, a recursion that is too deep for the stack. This lesson builds each traversal, shows those failures running, and stress tests the code against slow but obviously correct versions, as set up in the previous lesson.

The input usually gives n and m, then m lines with two vertex numbers each: an edge list. What you build from it decides what the algorithm can do quickly.

The adjacency list in C++ is a std::vector<std::vector<int>> where adj[u] holds the neighbors of u. A matrix of V = 10^5 vertices would need 10^10 entries, which is why it is out of the question for sparse graphs, while the list needs only V + 2E integers.

Two input conventions cause more wrong answers than the algorithms do:

• Numbering. Most statements number vertices from 1. Either subtract 1 as you read (as in this lesson) and add it back when you print, or allocate n + 1 entries and ignore index 0. Pick one and do it everywhere.
• Direction. An undirected edge ("a two-way link", "they are rivals") goes into both lists: adj[a].push_back(b) and adj[b].push_back(a). A directed edge ("a must come before b") goes into one. The pitfall section shows what happens when you mix them up.

Tram routes. A town's tram network has n stops and m two-way links between them (n, m <= 2*10^5). Find the fewest links needed to ride from stop s to stop t, and one such route, or print -1 if t cannot be reached.

Every link counts the same, so the question is about the number of edges on a path. Breadth-first search (BFS) answers it. Start with s at distance 0. Its neighbors are at distance 1. Their unvisited neighbors are at distance 2, and so on, layer by layer. A first-in first-out queue processes the vertices in exactly that order: all of layer k leaves the queue before any of layer k + 1. The first time a vertex is reached, it is reached by a shortest route, because every vertex of a smaller layer was processed earlier.

To print the route, remember for each vertex the one it was reached from (parent). Following parents back from t gives the route in reverse.

The input is n m s t, then the links:

Two routes from stop 1 lead towards 7: 1 2 4 5 7 with four links and 1 3 6 7 with three. BFS reaches stop 7 first through stop 6, which is in layer 2, so it reports three links. Every vertex enters the queue at most once and every adjacency list is scanned once, so this is O(V + E).

A map of cells is a graph too, with an edge between each pair of adjacent free cells. You do not need to build the adjacency list: the neighbors of cell (r, c) come from a direction table, a small array of row and column offsets. Looping over the table replaces four copies of almost the same code, and switching to 8 directions changes only the table.

Charging stations. A warehouse floor is a grid of free cells ., shelves # and charging stations C. A robot moves up, down, left or right. For each free cell, how many moves is the nearest charging station away?

Running BFS once from every station would cost O(stations * cells). Instead, put all the stations into the queue at distance 0 before the search starts. This multi-source BFS behaves as if there were one extra vertex connected to every station: each cell is reached first from the closest station, in one O(rows * cols) pass.

The left part of the map is served by the station in the top-left corner, the right part by the one in row 3. The top-right corner is 3 moves from the station in row 3; from the top-left station it could be reached only by a long detour through the bottom row, and the multi-source queue never even tries that detour. The cell marked - in the bottom row is boxed in by shelves, so no station reaches it. Always decide what to print for unreachable cells; the statement usually says.

Depth-first search (DFS) explores differently: from a vertex, follow one unvisited edge as far as possible, and only when stuck, back up and try the next edge. Recursion expresses this directly. DFS does not find shortest paths, but the order in which it starts and finishes vertices carries information that BFS does not have.

Record two timestamps per vertex: in when the search first enters it and out when it has finished everything reachable from it. If v is discovered while u is still open, v is a descendant of u, and its whole interval [in, out] lies inside u's. Topological sort and cycle detection below are built on these intervals.

The same search can also be written with an explicit stack instead of recursion. That matters because recursion depth is limited by the size of the call stack, which is fixed by the operating system and the judge. On a path graph 0 -> 1 -> ... -> n-1, recursive DFS nests n calls deep. With n = 10^5 or 10^6 and a few dozen bytes per call frame, that can exceed the stack (the Microsoft linker's default stack reservation, for example, is 1 MB), and the program crashes with no useful message, usually only on the largest test. The iterative version keeps a std::stack of pairs (vertex, index of the next neighbor to try) on the heap, so it reproduces the recursion step by step, with the same timestamps.

Vertices 4 and 5 are not reachable from 0, so the outer loop starts a second search from 4. Forgetting that loop is a classic bug: the program works whenever the test graph is connected. The last line shows the explicit stack growing to 10^5 entries on the path graph, which is harmless on the heap. The recursive version would need the same number of nested calls.

A connected component of an undirected graph is a maximal set of vertices that can all reach each other. To find them all, loop over the vertices and start a new BFS (or DFS) from each vertex that is not yet visited; each start is a new component. The total work is still O(V + E), because each vertex is visited once across all the searches.

A graph is bipartite if its vertices can be split into two groups with every edge going between the groups. BFS decides this while it traverses. Give the start vertex side A, every neighbor the opposite side of the vertex it was reached from, and check every edge: an edge between two vertices on the same side means no split exists. Such a conflict happens exactly when a component contains a cycle of odd length.

Two tables. At a dinner, n guests are seated at two tables, and m pairs of guests are rivals who must not sit at the same table. For each group of guests linked by rivalries, print a seating or say why it cannot work.

Guests 1 to 4 form a cycle of four rivalries, which alternates fine. Guests 5, 6 and 7 form a triangle: whoever sits at A, the other two must both sit at B, and they are rivals. Guest 8 has no rivals and forms a group alone, which the loop over all start vertices handles without a special case.

In a directed graph where an edge a -> b means "a must come before b", a topological order lists all vertices so that every edge points forward. It exists exactly when the graph has no directed cycle, that is, when it is a directed acyclic graph (DAG).

Build order. A project has n modules and m rules "module a must be built before module b". Print an order that respects all rules, or, if none exists, a cycle of rules that makes it impossible.

Kahn's algorithm (A. B. Kahn, 1962) works like a build tool. Count for each module how many unbuilt modules it still waits for (its in-degree). Every module with in-degree 0 can be built now; build one, and decrease the in-degree of everything that waited for it. If modules remain but none has in-degree 0, every remaining module waits for another remaining one, which means there is a cycle. So Kahn's algorithm both sorts and detects cycles: the order it produces is shorter than n exactly when the graph has a cycle.

The DFS-based method uses finishing times instead: in a DAG, listing vertices in decreasing out time gives a topological order, because every edge u -> v has v finished before u. DFS is also the natural way to find an actual cycle. Color vertices white (not visited), gray (on the current path of the search) and black (finished). An edge to a gray vertex leads back to a vertex on the current path, so it closes a cycle, and the parent links spell it out.

The first sample is acyclic; the second adds the rule 5 2, which closes the loop 2 -> 4 -> 5 -> 2.

Kahn's queue starts with modules 1 and 6, both of which need nothing, and the rest follows. A topological order is usually not unique: 6 1 3 2 4 5 would be just as valid. If a problem asks for the smallest order in dictionary order, replace the queue with a min-priority queue (std::priority_queue<int, std::vector<int>, std::greater<>>), which costs an extra log V per vertex.