Graph Theory
Before the algorithms, the shapes. Eight kinds of graph — directed and undirected, weighted and not, complete, bipartite, cyclic, and the all-important DAG — and how each property decides what you're allowed to do with the graph.
What is Graph Theory?
The 60-second primer
A graph is the simplest way to say 'these things are related.' Dots for the things — call them vertices or nodes — and lines for the relationships — call them edges. That's the entire definition. Friendships, roads, web links, course prerequisites, circuit wires, molecules, git commits: every one of them is a set of things plus a set of connections, which is to say every one of them is a graph.
The reason graphs are worth a whole topic before you touch a single algorithm is that not all graphs are the same shape — and the shape decides what you're allowed to do. Do the edges point one way or both? Do they carry a number, or are they all equal? Can you walk in a circle, or does every path eventually dead-end? Is the graph one big blob, or two neat sides? Each of these is a yes/no question, and the answers are what people mean when they say directed, weighted, cyclic, bipartite, complete. Learn to read those properties off a graph and half of graph theory stops being vocabulary and starts being obvious.
This topic walks the properties in the order they build on each other. First direction — undirected versus directed, the most fundamental fork. Then weight — unweighted versus weighted, which changes what 'shortest' even means. Then the special families — complete graphs at one density extreme, bipartite graphs split cleanly in two. Finally cycles — graphs that loop back, and the acyclic ones (DAGs) that don't, which are the single most important graph shape in all of software engineering. Every prototype here is something you can drive: build the graph, run the test, watch the property reveal itself.
Why the shape matters before the algorithm
- The shape picks the algorithm. Shortest path in an unweighted graph is BFS; add weights and it becomes Dijkstra. Ordering tasks works only if the dependency graph is a DAG. You can't choose the right tool until you've named the shape.
- The shape catches bugs. 'Can A reach B?' has a different answer in a directed graph than an undirected one. Treating a one-way street network as two-way silently returns wrong routes — a class of bug that only makes sense once you know direction is a property.
- Modelling is a shape decision. When you sit down to represent a problem as a graph, your first three questions are exactly these: directed or not, weighted or not, can it cycle? Get them right and the data structure writes itself.
- Real systems are named by their shape. A build system is 'a DAG of targets.' A scheduler runs 'a topological order.' A matching engine works on 'a bipartite graph.' The shape is the shared language engineers use to describe these systems.
- Impossibility is a shape, too. 'There is no valid build order' is the same statement as 'the dependency graph has a cycle.' Recognising the shape tells you when a problem has no solution before you waste time looking for one.
Two ways to store any of these graphs
Whatever the shape, you store it one of two ways. An adjacency list keeps, per node, the list of its neighbours — O(V + E) memory, fast to iterate, the default for the sparse graphs you meet in practice. An adjacency matrix is a V×V grid where cell (u, v) marks the edge (and holds its weight, if any) — O(V²) memory but O(1) to ask 'is there an edge from u to v?'. Direction shows up as asymmetry in the matrix; weight shows up as numbers instead of 1/0; an undirected graph's matrix is symmetric.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Graph type | Edges | Weighted? | Cycles? | Models / where it shows up |
|---|---|---|---|---|
01Undirected | Two-way | No | Allowed | Friendships, road links you can travel both ways, network cables, mutual relationships. |
02Directed (digraph) | One-way | No | Allowed | Twitter follows, web links, one-way streets, state machines, prerequisites. |
03Unweighted | Either | No — all edges equal | Allowed | Fewest-hops questions: degrees of separation, maze steps, BFS distance. |
04Weighted | Either | Yes — each edge has a cost | Allowed | Road distances, network latency, prices — anywhere 'cheapest' ≠ 'fewest'. |
05Complete (Kₙ) | Every pair | Either | Many | Round-robin tournaments, fully-connected layers, the dense worst case. |
06Bipartite | Only across two sides | Either | Even-length only | Jobs↔workers, students↔courses, any matching problem. |
07Cyclic | Either | Either | Has at least one | Feedback loops, deadlocks, circular dependencies, money-laundering rings. |
08DAG (acyclic) | One-way | Either | None — by definition | Build systems, task schedulers, spreadsheets, git history, course plans. |
- Edges
- Two-way
- Weighted?
- No
- Cycles?
Allowed- Models / where it shows up
- Friendships, road links you can travel both ways, network cables, mutual relationships.
- Edges
- One-way
- Weighted?
- No
- Cycles?
Allowed- Models / where it shows up
- Twitter follows, web links, one-way streets, state machines, prerequisites.
- Edges
- Either
- Weighted?
- No — all edges equal
- Cycles?
Allowed- Models / where it shows up
- Fewest-hops questions: degrees of separation, maze steps, BFS distance.
- Edges
- Either
- Weighted?
- Yes — each edge has a cost
- Cycles?
Allowed- Models / where it shows up
- Road distances, network latency, prices — anywhere 'cheapest' ≠ 'fewest'.
- Edges
- Every pair
- Weighted?
- Either
- Cycles?
Many- Models / where it shows up
- Round-robin tournaments, fully-connected layers, the dense worst case.
- Edges
- Only across two sides
- Weighted?
- Either
- Cycles?
Even-length only- Models / where it shows up
- Jobs↔workers, students↔courses, any matching problem.
- Edges
- Either
- Weighted?
- Either
- Cycles?
Has at least one- Models / where it shows up
- Feedback loops, deadlocks, circular dependencies, money-laundering rings.
- Edges
- One-way
- Weighted?
- Either
- Cycles?
None — by definition- Models / where it shows up
- Build systems, task schedulers, spreadsheets, git history, course plans.
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
Reading a graph's shape — the questions in order
- Do the edges have direction? If a connection is mutual (friendship, a cable), it's undirected. If it can be one-way (a follow, a link, a prerequisite), it's directed — and now 'A reaches B' no longer implies 'B reaches A'.
- Do the edges carry a number? If every edge is interchangeable, it's unweighted and 'shortest' means fewest edges — use BFS. If edges have costs, it's weighted and 'shortest' means lowest total cost — a 3-hop cheap path can beat a 1-hop expensive one, which is exactly why Dijkstra exists.
- How dense is it? A graph where every pair is connected is complete (Kₙ) and has n(n−1)/2 edges — the ceiling. Most real graphs are far sparser; knowing where you sit on that scale tells you whether an adjacency list or matrix wins.
- Can the nodes split into two sides with no edge inside a side? Then it's bipartite, and matching algorithms apply. The quick test: try to 2-colour it; you succeed if and only if it has no odd-length cycle.
- Can you start at a node and walk back to it? If yes, the graph is cyclic — watch for feedback loops and deadlocks. If a directed graph never lets you loop back, it's a DAG, and you get a topological order for free.
DAG is the property that pays the rent
Of all these shapes, 'directed and acyclic' is the one you'll lean on most as an engineer. A DAG is exactly the condition under which you can list everything in an order where every dependency comes before the thing that needs it — a topological order. Build systems, package managers, spreadsheet recalculation, data pipelines, and even the way git stores commits are all DAGs precisely so this ordering is guaranteed to exist. The moment a cycle sneaks in, the order vanishes and the tool reports an error — 'circular dependency.'
Concepts in this track
8 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
Undirected Graphs
Vertices joined by two-way edges — the plainest graph there is. Meet degree, paths, components, and the handshake lemma.
Directed Graphs
Give each edge an arrow and 'connected' splits into in-degree and out-degree — A reaching B no longer means B reaches A.
Unweighted Graphs
Every edge counts the same, so 'shortest path' means fewest hops — and BFS reads the distance off in expanding rings.
Weighted Graphs
Put a cost on every edge and the cheapest route stops being the one with the fewest hops. The shape that makes Dijkstra necessary.
Complete Graphs (Kₙ)
Every node joined to every other. The densest graph possible — exactly n(n−1)/2 edges — and the worst case every algorithm fears.
Bipartite Graphs
Nodes split into two sides with edges only crossing between them. Two-colourable exactly when there's no odd cycle.
Cyclic Graphs
A graph you can walk in a circle. Spotting the loop — the back edge to a node still on the stack — is the whole game.
Directed Acyclic Graphs
Directed, with no way to loop back. The shape behind build systems and schedulers — it always has a topological order.
Related tracks
If this one clicks, try these next.
Trees
The branching data structure under databases, filesystems, autocompletes, and priority queues. Nine trees, from the plain binary search tree through the self-balancing workhorses to the disk-friendly B-trees and the range-query structures competitive programmers swear by.
Graph Algorithms
How computers reason about networks of things — roads, friends, packets, dependencies. Ten algorithms, from the two traversals every other algorithm is built on, to weighted shortest paths, minimum spanning trees, and the heuristic search behind every modern pathfinder.
Sorting
Order a list — ten ways. From the textbook swap-adjacent sorts you write in a single loop, to the divide-and-conquer giants, to the non-comparison tricks that beat O(n log n), to the hybrid your language's sort() actually uses.