The Concept#
A graph is one of the most general data structures in computer science: a collection of vertices (also called nodes) connected by edges. Almost any relationship can be modelled as a graph: cities linked by roads, web pages linked by hyperlinks, tasks linked by dependencies, people linked by friendships.
Formally, a graph G = (V, E) where V is the set of vertices and E is the set of edges. Everything else (directed vs. undirected, weighted vs. unweighted, cyclic vs. acyclic) is a variation on this simple skeleton.
Directed vs. Undirected#
In an undirected graph, every edge is a two-way street: if there is an edge between A and B, you can travel from A to B and from B to A. Friendship graphs are typically undirected.
In a directed graph (digraph), edges have a direction. An arrow from A to B does not imply one from B to A. Web links, Twitter follows, and task-dependency graphs are all directed.
Weighted vs. Unweighted#
A weighted graph attaches a numeric value (the weight) to each edge. Road networks are weighted by distance or travel time; communication networks by bandwidth or latency. An unweighted graph treats all edges as equal, which is useful when you only care about connectivity, not cost.
Representing a Graph in Code#
There are two standard representations, and the right choice depends on how dense your graph is.
Adjacency List (O(V + E) space)#
Store, for each vertex, the list of its neighbours. In Python this is naturally a dictionary mapping each vertex to a list of (or set of) neighbours.
Pros: space-efficient for sparse graphs (most real-world graphs), fast iteration over a vertex's neighbours (proportional to its degree), easy to extend edges with weights by storing (neighbour, weight) tuples.
Cons: checking whether a specific edge (u, v) exists takes O(degree(u)) time.
Adjacency Matrix (O(V²) space)#
A 2D boolean (or weight) array where matrix[u][v] = True (or the edge weight) if an edge exists from u to v.
Pros: O(1) edge existence check; straightforward to implement for small graphs.
Cons: wastes O(V²) space even if the graph has very few edges; iterating over all neighbours of a vertex is always O(V).
Rule of thumb: use an adjacency list unless you need constant-time edge lookup or the graph is small and dense.
Traversals: BFS and DFS#
Two fundamental algorithms for visiting every reachable vertex in a graph:
Breadth-First Search (BFS) uses a queue and explores vertices in order of their distance from the source: all vertices one hop away, then two hops, and so on. Because of this level-by-level expansion, BFS finds the shortest path (in terms of edge count) from a source to every reachable vertex in an unweighted graph.
Depth-First Search (DFS) uses a stack (or the call stack via recursion) and goes as deep as possible along each branch before backtracking. DFS is the foundation for cycle detection, topological ordering of directed acyclic graphs (DAGs), and finding connected components.
Both BFS and DFS visit every vertex once and examine every edge (in the undirected adjacency-list representation here, each edge is examined from both endpoints), giving O(V + E) time complexity.
Code Implementation#
Complexity Analysis#
| Representation | Space | Edge exists? | Iterate neighbours |
|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(degree) |
| Adjacency matrix | O(V²) | O(1) | O(V) |
| BFS / DFS traversal | O(V + E) time, O(V) queue/stack | n/a | n/a |
Interactive Labs#
Both labs run on the same six-vertex undirected graph: vertices A to F, nine edges (A-B, A-D, B-C, B-D, B-E, C-E, D-E, D-F, E-F), with A as the source (green) and E as the target (red). Same graph, same starting point. The only thing that changes is the container holding the frontier.
Let's take that graph and run BFS on it. A queue makes the frontier expand in concentric rings: A first, then everything one hop away (B and D), then everything two hops away. Watch it stop the instant E is dequeued, and note the path it lights up: A → B → E, two edges. BFS guarantees no shorter one exists.
Now the same graph with a stack instead. DFS commits to one branch and drives it to the bottom: from A it takes B, from B it takes C, and C is a dead end, because both of C's neighbours are already visited. Watch the traversal retract to B and only then discover E. Same two-edge answer here, but arrived at by depth, not by distance. On a larger graph the two orders diverge sharply.
What to Remember#
- Graph = vertices + edges. Everything else (directed, weighted, cyclic) is a flavour of this skeleton.
- Adjacency list for sparse graphs, matrix for dense graphs. Most real-world graphs are sparse; adjacency lists are the default.
- BFS = shortest path in unweighted graphs. Its level-by-level expansion guarantees the first time it reaches a vertex it has used the minimum number of edges.
- DFS = deep exploration. Cycle detection, topological sort, and connected components all rely on DFS's ability to follow a path all the way to its end before backtracking.
- Both run in O(V + E). The combined cost is linear in the size of the graph regardless of its shape.
- BFS and DFS are covered in depth in their own dedicated articles, which immediately follow this one in the roadmap. The Dijkstra and Bellman-Ford articles after those assume you are comfortable with both traversals.