Graph Basics and Representation
DSA · Graphs
Theory
A graph is a set of vertices (nodes) connected by edges. Edges can be directed (one-way, like follows on social media) or undirected (two-way, like roads), and weighted (with a cost such as distance) or unweighted. Graphs are stored as an adjacency list (each vertex keeps a list of neighbours, O(V + E) space) or an adjacency matrix (a V × V grid, O(V²) space but O(1) edge checks).
Why we use it
Graphs model networks of relationships: maps, social networks, dependencies between tasks, and web links.
When to use it
Use an adjacency list for most sparse real-world graphs; use a matrix for small dense graphs or when you need constant-time edge lookups.
How it works
- Vertices V, edges E
- Dense graph? Yes: Adjacency matrix (V x V). No: Adjacency list (dict of lists).
- Edges have weights? Yes: Store (neighbour, weight). No: Store neighbour.
- Choose directed or undirected
Syntax
Adjacency list: graph = {"A": ["B", "C"], "B": ["A"], ...}
Adjacency matrix: m[i][j] = 1 (or weight) if edge i->j
List: space O(V+E), neighbours O(degree)
Matrix: space O(V²), edge check O(1)Example
edges = [("Delhi", "Jaipur"), ("Delhi", "Agra"), ("Agra", "Lucknow"), ("Jaipur", "Agra")]
graph = {}
for a, b in edges: # undirected
graph.setdefault(a, []).append(b)
graph.setdefault(b, []).append(a)
for city in graph:
print(city, "->", graph[city])
names = sorted(graph)
idx = {n: i for i, n in enumerate(names)}
matrix = [[0] * len(names) for _ in names]
for a, b in edges:
matrix[idx[a]][idx[b]] = matrix[idx[b]][idx[a]] = 1
print(names)
for row in matrix:
print(row)Key points
- Vertices connected by edges
- Directed vs undirected, weighted vs unweighted
- Adjacency list for sparse graphs
- Adjacency matrix for dense graphs