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 — 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 and edge exactly once, 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 | — | — |
Interactive Labs
BFS explores the graph level by level, discovering all vertices at distance 1 before distance 2, and so on. Notice how the frontier expands in concentric rings outward from the source.
DFS dives down a single path as far as it can go before backtracking. Watch how it exhausts an entire branch before doubling back to explore siblings.
Key Takeaways
- 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.