Graphs / representation, traversal, shortest paths / interactive
Things, and the connections between them
Drop the rule that every node has one parent and at most two children, and a tree becomes a graph: any set of things, connected however you like. That freedom costs you the two guarantees a tree gave for free — no root to start from, and no promise that following edges won't take you in a circle. Almost everything below is a strategy for coping with those two facts.
What a graph is
Vertices and edges. Everything else is vocabulary for describing how they happen to be arranged.
Networks
Road maps, flight routes, the internet itself. Shortest-path and max-flow problems are literally these.Dependencies
Build systems, package managers, course prerequisites, Maven modules. A cycle here is a fatal error, not a curiosity.Relationships
Social graphs, citations, recommendations. "People you may know" is a two-hop neighbourhood query.State spaces
Every position in a puzzle is a vertex; every legal move an edge. Solving it is a shortest-path search.Four flavours, one structure
These properties combine freely, and each one changes which algorithms apply.
Property 01
Directed or not
An undirected edge is really two directed edges. "Follows" is directed; "is married to" is not. Directed graphs need indegree and outdegree counted separately.
Property 02
Weighted or not
A number on each edge — distance, cost, capacity. Without weights, "shortest" means fewest edges and BFS solves it. With weights you need Dijkstra.
Property 03
Cyclic or acyclic
A directed acyclic graph (DAG) can be topologically sorted — laid out so every edge points forward. That is exactly what a build system does.
Property 04
Connected or not
A graph can be several islands. One traversal only reaches one component, so counting components means looping over every unvisited vertex.
A tree is just a connected, acyclic, undirected graph — and a rooted tree is one where you have nominated a starting vertex. Everything you know about tree traversal is graph traversal with the cycle problem already solved for you.
How you store one
Two representations, and the choice governs the cost of every algorithm you run afterwards.
The graph
Adjacency matrix O(V²) space
A V×V grid of booleans. hasEdge(u,v) is one array lookup — but the row for a vertex with two neighbours still occupies all seven columns, and 93% of this grid is zeros.
Adjacency list O(V + E) space
One list of neighbours per vertex. Storage is proportional to the edges that actually exist, and iterating a vertex's neighbours — the inner loop of every traversal — touches only them.
The trade is the same one arrays and linked lists make, one dimension up. A matrix is a dense block: constant-time random access, space you pay for whether you use it or not. A list is a chain per vertex: space proportional to reality, but answering "is there an edge from u to v?" means scanning u's neighbours.
Almost every real graph is sparse. A road network has maybe four edges per intersection, not thousands. A social graph with a billion users has nowhere near a billion-squared friendships. That is why adjacency lists are the default, and why traversal is quoted as O(V + E) — you visit every vertex once and walk every edge once.
Reach for a matrix when the graph is genuinely dense, when V is small and fixed, or when the algorithm needs constant-time edge tests in an inner loop — Floyd–Warshall, for instance, is written directly against the matrix.
| Operation | Matrix | List |
|---|---|---|
| space | O(V²) | O(V + E) |
| hasEdge(u,v) | O(1) | O(deg u) |
| neighbours(u) | O(V) | O(deg u) |
| addEdge | O(1) | O(1) |
| removeEdge | O(1) | O(deg u) |
| BFS / DFS | O(V²) | O(V + E) |
Traversal
Breadth first, depth first
Two orders of visiting everything reachable. They are the same twelve lines of code — the only difference is what you keep the frontier in.
This is the whole distinction. Take a vertex out of the frontier, mark it seen, put its unseen neighbours back in. If the frontier is a queue, the oldest waiting vertex comes out first and you sweep outward level by level — that is BFS. Swap it for a stack and the newest one comes out first, so you charge down one path until it dead-ends — that is DFS.
Nothing else changes. Not the visited set, not the neighbour loop, not the termination condition. It is worth writing both once with the container as a parameter, just to watch the behaviour flip.
The visited set is not optional. A tree traversal can omit it because there is exactly one path to each node. A graph has cycles, so without it the traversal revisits vertices forever. Mark a vertex when you enqueue it, not when you dequeue it, or the same vertex enters the frontier several times before it is ever processed.
| BFS | DFS | |
|---|---|---|
| frontier | queue | stack |
| visits | nearest first | deepest first |
| extra space | O(width) | O(depth) |
| finds | fewest-edge paths | any path |
| natural form | iterative | recursive |
| good for | shortest hops, levels, nearest match | cycles, topological sort, components, backtracking |
Shortest paths
Getting there cheapest
Without weights, the nearest unvisited vertex is simply the next one in the queue. With weights, you have to keep changing your mind.
Reference code
Java, adjacency-list based. The traversals differ by one word.
Mark on enqueue
Not on dequeue. Otherwise a vertex reachable by three edges enters the frontier three times, and the traversal degrades badly on dense graphs.Store parents, not paths
Keep aparent[] array and walk it backwards at the end. Copying a path into every queue entry is O(V) memory per entry.