Non-Linear Data Structures
Graphs
Vertices connected by edges — the most general way to model relationships and networks.
1Introduction
Maps, social networks, the web, course prerequisites and computer networks are all graphs. Learning to model a problem as a graph unlocks a huge toolbox: BFS, DFS, shortest paths, spanning trees and topological sorting.
2What is it?
A graph G = (V, E) is a set of vertices V and a set of edges E connecting pairs of vertices. Edges can be undirected (friendship) or directed (follows), and weighted (distance) or unweighted.
3Why do we use it?
- Model any network of relationships.
- Find shortest routes and connectivity.
- Schedule tasks with dependencies.
- Detect cycles and communities.
4Real-world examples
- Road maps and GPS navigation.
- Social networks (friends, followers).
- Web pages and hyperlinks.
- Course prerequisites.
5Internal working
Adjacency list: for every vertex, a list of its neighbours. Space O(V + E) — best for sparse graphs.
Adjacency matrix: a V × V table where cell [u][v] marks an edge. O(1) edge lookup but O(V²) space.
Traversals keep a visited set so each vertex is processed once, even when the graph has cycles.
6Memory representation
Undirected graph and its adjacency list:
A --- B --- D
| | |
C E G
\ / /
F ------
A: [B, C] B: [A, D, E] C: [A, F]
D: [B, G] E: [B, F] F: [C, E, G]
G: [D, F]7Operations
| Operation | How it works |
|---|---|
| Add vertex | New empty adjacency list. |
| Add edge | Append to both lists (undirected). |
| Check edge (u, v) | Scan u's list (matrix: O(1)). |
| BFS / DFS | Every vertex and edge once. |
| Shortest path (unweighted) | BFS distances. |
8Visual explanation
Queue (front → rear)
Traversal order
Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
function bfs(graph, start) {
const visited = new Set([start]);
const dist = { [start]: 0 };
const queue = [start];
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
dist[neighbor] = dist[node] + 1;
queue.push(neighbor);
}
}
}
return { order, dist };
}
const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
(graph[u] ??= []).push(v);
(graph[v] ??= []).push(u);
}
const { order, dist } = bfs(graph, "A");
console.log("BFS order:", order.join(" -> "));
console.log("Distances:", order.map((v) => v + "=" + dist[v]).join(", "));
10Time complexity
| Operation | Time |
|---|---|
| Add vertex | O(1) |
| Add edge | O(1) |
| Check edge (u, v) | O(deg u) |
| BFS / DFS | O(V + E) |
| Shortest path (unweighted) | O(V + E) |
11Space complexity
Adjacency lists use O(V + E); adjacency matrices use O(V²). BFS/DFS need O(V) extra space for the visited set and queue/stack.
12Advantages
- Extremely expressive.
- Rich set of well-studied algorithms.
- Adjacency lists are compact for sparse graphs.
13Disadvantages
- Many algorithms are complex to implement correctly.
- Dense graphs are memory-heavy.
- Cycles require careful visited tracking.
14Common mistakes
- Forgetting to mark vertices visited → infinite loops on cycles.
- Marking visited on dequeue in BFS (vertices get enqueued multiple times).
- Adding an undirected edge in only one direction.
- Ignoring disconnected components (loop over all vertices).
- Using BFS for shortest paths in weighted graphs (use Dijkstra).
15Interview questions
16Practice exercises
- Count connected components.
- Detect a cycle in an undirected graph.
- Check whether a graph is bipartite.
- Find the shortest path in a grid with obstacles.
- Clone a graph.
Try them in the Coding Playground.