A tree says each node has exactly one parent and there are no cycles. Drop both rules and you have a graph, which is the most general of these structures and the one that models the most real situations.
The vocabulary#
- vertex (or node): a thing. A person, a city, a web page, a course.
- edge: a connection between two of them.
- directed: the edge goes one way. "A follows B" does not mean B follows A.
- undirected: it goes both ways. "A and B are friends."
- weighted: each edge carries a number, such as a distance or a cost.
- cycle: a path that gets back to where it started.
Almost any "what connects to what" question is a graph question. Road networks, dependencies between tasks, friendships, the web, course prerequisites. The lesson you are reading has prerequisites, which makes this track a graph too.
Writing one down#
Adjacency list. For each vertex, the list of vertices it connects to.
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> []
Memory is O(V + E), meaning it grows with the vertices plus the edges. This is what you want almost always, because real graphs are sparse: a social network with a billion people does not have anyone holding a billion friendships.
Adjacency matrix. A V by V grid where grid[a][b] says whether an edge exists.
Memory is O(V squared) whether or not the edges are there. Checking "is there an edge from a to b" is instant, which occasionally matters, but a million vertices would need a trillion cells. Use it for small dense graphs and not otherwise.
Walking one#
You will use two, and they differ by one line.
Depth first search follows one path as far as it goes, then backs up and tries the next. It uses a stack, either one you manage or the call stack via recursion.
Breadth first search visits everything one step away, then everything two steps away. It uses a queue.
start at 0, edges 0->1, 0->2, 1->3, 2->3
depth first: 0, 1, 3, 2
breadth first: 0, 1, 2, 3
Both are O(V + E): every vertex is visited once and every edge is looked at once.
The one thing you must not forget#
Keep a visited set.
A tree has no cycles, so walking one terminates naturally. A graph can have cycles, and a walk without a visited set goes round one forever. This is the commonest graph bug there is, and it does not fail loudly; it hangs.
Mark a vertex visited when you first reach it, not when you finish with it, or you can queue the same vertex several times before processing any of them.
Why the choice of walk matters#
Breadth first search reaches every vertex at distance 1 before any at distance 2. So the first time it reaches a vertex, it did so by the shortest route. That is a real guarantee and it is why breadth first search finds shortest paths in unweighted graphs.
Depth first search offers no such thing. It will find a path, and it can be arbitrarily bad.
Once edges have weights, breadth first search stops working too, because three cheap steps can beat one expensive one. That is what Dijkstra's algorithm is for, and it is breadth first search with a heap in place of the queue, always expanding the cheapest known vertex next.
What each walk is good for#
Depth first: detecting cycles, topological ordering, finding connected components, flood fill, and anything where you need to finish exploring one branch before judging it.
Breadth first: shortest path with equal step costs, finding everything within k steps, level by level processing.
Topological order#
If the edges mean "this must happen before that", you often want an order respecting all of them. Course prerequisites, build dependencies, task scheduling.
This is only possible if there are no cycles. If A needs B and B needs A, no order exists, and the algorithm that looks for one is also the algorithm that detects the impossibility. That is why "can these courses be finished" and "is there a cycle" turn out to be the same question.
Common mistakes#
- No visited set, so a cycle becomes an infinite loop.
- Marking visited on dequeue rather than on enqueue, so vertices get queued repeatedly.
- Using depth first search for a shortest path.
- Using breadth first search on a weighted graph and expecting the cheapest path.
- Assuming the graph is connected. It may be several separate pieces, so one walk from one start may not reach everything.
Where this goes next#
The two walks get a lesson of their own, the next one in this track, because the choice between them is what decides whether a search can answer "shortest". The mistakes listed above are all made there, on real problems, where they are easier to remember.