DSA · Chapter 24 of 40
Graphs
A graph is a set of vertices connected by edges. Edges can be directed or undirected, weighted or unweighted, and the graph may contain cycles. Social networks, road maps and dependency systems are all graphs.
The two standard representations are an adjacency list (a map from vertex to its neighbours) and an adjacency matrix (a 2D grid of 0/1 or weights).
Adjacency list vs matrix
A list uses O(V + E) memory and is best for sparse graphs. A matrix uses O(V^2) memory but checks whether an edge exists in O(1).
Terminology
Degree is the number of edges at a vertex, a path is a sequence of connected vertices, and a connected component is a group of mutually reachable vertices.
Example 1 (python)
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}
print(graph['A'])Output
['B', 'C']An adjacency list maps each vertex to its neighbours.
Example 2 (python)
# adjacency matrix for 3 vertices
m = [[0, 1, 0],
[1, 0, 1],
[0, 1, 0]]
print(m[1][2]) # is there an edge 1-2?Output
1Edge lookup is O(1) but memory is O(V^2).
Key points
- Graphs have vertices and edges, possibly directed or weighted.
- Adjacency lists suit sparse graphs; matrices suit dense ones.
- Cycles and disconnected components are common cases to handle.
- Trees are just connected acyclic graphs.
💡 Note: Always ask whether the graph is directed and whether it can contain cycles.