What a graph is
A graph is a set of nodes (vertices) joined by edges. It is the most general structure there is: a tree is just a graph with no cycles, and almost anything that connects — roads between cities, friends on a network, web pages linking to each other, tasks depending on tasks — is naturally a graph.
Edges come in flavours. A directed edge points one way (follows on social media); an undirected one goes both (a road). A weighted edge carries a number — a distance, cost or time. And a graph may contain cycles, which is exactly what trees forbid.
Two ways to store one
How you represent a graph decides which operations are cheap. An adjacency list keeps, for each node, a list of its neighbours — compact when edges are few (a sparse graph), which is most real graphs. An adjacency matrix is an n×n grid where cell (i, j) marks an edge — instant to check "is there an edge?" but it uses n² space whether the graph is dense or not.
| Representation | Space | Check edge (i,j) | List neighbours | Best for |
|---|---|---|---|---|
| Adjacency list | O(n + e) | O(degree) | O(degree) | sparse graphs (most) |
| Adjacency matrix | O(n²) | O(1) | O(n) | dense graphs, quick edge tests |
Walking a graph: BFS and DFS
The two fundamental traversals differ only in the structure that holds the nodes waiting to be visited. Breadth-first search uses a queue, so it fans out level by level — visiting all immediate neighbours, then their neighbours. On an unweighted graph that makes it find the fewest-edges path to every node.
Depth-first search uses a stack (often via recursion), so it plunges as deep as possible down one branch before backing up. DFS is the natural fit for detecting cycles, finding connected components, and topological ordering.
Same algorithm, one data structure apart
Swap the queue in BFS for a stack and you get DFS. That single change — FIFO versus LIFO — is the whole difference between exploring broad and exploring deep.
The classic algorithms
On weighted graphs, a handful of named algorithms come up again and again:
| Problem | Algorithm | In one line |
|---|---|---|
| Shortest path (non-negative weights) | Dijkstra | grow outward, finalising the nearest unvisited node next |
| Cheapest way to connect everything | Prim / Kruskal (MST) | pick the lightest edges that add no cycle |
| Order tasks by dependency | Topological sort | on a DAG, list nodes so every edge points forward |
| Fewest hops (unweighted) | BFS | level-by-level from the start |
Dijkstra, a little closer
Dijkstra is the one worth understanding well. It keeps a frontier of tentative distances in a priority queue and repeatedly finalises the closest unvisited node, then relaxes its neighbours — updating their tentative distances if going through this node is shorter. The heap from the previous lesson is exactly what makes it efficient. It assumes non-negative weights; negative edges need a different algorithm (Bellman-Ford).
A worked example
From node A, edges are A–B, A–C, B–D, C–D. Give a BFS order and a DFS order starting at A, and say which finds the shortest hop-count to D.
- BFS (queue): visit A, then its neighbours B and C, then D. Order: A, B, C, D.BFS fans out level by level, so D (two hops away) is reached last.
- DFS (stack/recursion): A → B → D, back up, then C. Order: A, B, D, C.DFS dives down one branch (A-B-D) before exploring C.
- BFS gives the shortest hop-count: A to D in 2 edges.On an unweighted graph, BFS reaches every node by a fewest-edges path.
BFS: A, B, C, D; DFS: A, B, D, C. BFS establishes the shortest hop-count (2) to D.