Chapter 30: DSA Graphs Implementation
DSA Graphs Implementation – Let’s learn this topic properly, like I’m sitting next to you with a whiteboard, drawing examples step by step, explaining every detail slowly and clearly, showing code in multiple styles, comparing pros & cons, and most importantly telling you which implementation you should actually choose in interviews and real projects.
What does “Graph Implementation” mean?
When we say “graph implementation”, we are talking about how to store and represent a graph in computer memory so that we can efficiently:
- Add vertices
- Add/remove edges
- Check if two vertices are connected
- Traverse the graph (DFS, BFS, Dijkstra, etc.)
There are two main ways to implement (represent) a graph in code:
- Adjacency Matrix
- Adjacency List
And there are some specialized variants (edge list, incidence matrix, etc.) that appear occasionally in advanced topics.
Almost every interview and almost every real project uses one of these two.
1. Adjacency Matrix Implementation
What it is: A 2D array (matrix) where:
- Rows and columns represent vertices
- matrix[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j
- matrix[i][j] = 0 if no edge
Example – Undirected graph with 4 vertices (A, B, C, D)
Vertices: 0 = A, 1 = B, 2 = C, 3 = D
Edges: A–B, A–C, B–D, C–D
Adjacency Matrix:
|
0 1 2 3 4 5 6 7 8 9 10 |
0 1 2 3 ← columns (to) 0 [0 1 1 0] ← row 0 (from A) 1 [1 0 0 1] 2 [1 0 0 1] 3 [0 1 1 0] |
Code – Adjacency Matrix (Python)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class GraphMatrix: def __init__(self, vertices): self.V = vertices self.graph = [[0] * vertices for _ in range(vertices)] def add_edge(self, u, v): # undirected graph → symmetric self.graph[u][v] = 1 self.graph[v][u] = 1 def print_graph(self): for row in self.graph: print(row) # Usage g = GraphMatrix(4) # vertices 0,1,2,3 g.add_edge(0, 1) # A-B g.add_edge(0, 2) # A-C g.add_edge(1, 3) # B-D g.add_edge(2, 3) # C-D g.print_graph() |
Advantages of Adjacency Matrix
- Checking if edge exists → O(1)
- Very easy to implement for dense graphs
- Good for weighted graphs (store weight instead of 1)
- Easy to implement Floyd-Warshall algorithm
Disadvantages
- Space complexity → O(V²) → very bad if graph is sparse (few edges)
- Adding vertex → difficult (need to resize entire matrix)
When to use matrix (rare in practice):
- Small number of vertices (V ≤ 100–500)
- Need very fast edge lookup
- Graph is dense (almost complete)
- Implementing algorithms like Floyd-Warshall
2. Adjacency List Implementation (most common & most recommended)
What it is: Each vertex keeps a list (or set) of vertices it is directly connected to.
Example – same graph as above
|
0 1 2 3 4 5 6 7 8 9 10 11 |
graph = { 0: [1, 2], # A → B, C 1: [0, 3], # B → A, D 2: [0, 3], # C → A, D 3: [1, 2] # D → B, C } |
Code – Adjacency List (Python – most common interview style)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Graph: def __init__(self): self.graph = {} # dictionary: vertex → list of neighbors def add_vertex(self, v): if v not in self.graph: self.graph[v] = [] def add_edge(self, u, v): self.add_vertex(u) self.add_vertex(v) # undirected graph self.graph[u].append(v) self.graph[v].append(u) def print_graph(self): for vertex in self.graph: print(f"{vertex} → {self.graph[vertex]}") # Usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 3) g.add_edge(2, 3) g.print_graph() # Output: # 0 → [1, 2] # 1 → [0, 3] # 2 → [0, 3] # 3 → [1, 2] |
For Weighted Graph – store pairs (neighbor, weight)
|
0 1 2 3 4 5 6 7 8 9 10 |
graph = { 0: [(1, 4), (2, 8)], # from 0 to 1 cost 4, to 2 cost 8 1: [(0, 4), (3, 2)], # ... } |
Comparison – Adjacency Matrix vs Adjacency List
| Question / Property | Adjacency Matrix | Adjacency List (recommended) |
|---|---|---|
| Space Complexity | O(V²) | O(V + E) |
| Add edge | O(1) | O(1) |
| Check if edge exists | O(1) | O(degree) or O(1) with set |
| Iterate over neighbors | O(V) | O(degree) – much faster |
| Good for dense graph? | Yes | No (wastes space) |
| Good for sparse graph? | No | Yes (most real graphs) |
| Used in interviews? | Sometimes (small V) | Almost always |
| Used in real projects? | Rarely | Very often |
Rule of thumb (2025–2026 style):
Use Adjacency List unless the problem specifically says small number of vertices (V ≤ 400–500) or requires Floyd-Warshall.
Bonus: Other Less Common Representations
- Edge List Just list of all edges: [(0,1), (0,2), (1,3), …] Used in Kruskal’s algorithm for MST
- Incidence Matrix Rows = vertices, Columns = edges Rarely used in competitive programming
Summary – Graph Implementation Cheat Sheet
| Representation | Space | Edge check | Neighbor iteration | Best for |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) | Dense, small V |
| Adjacency List | O(V+E) | O(degree) | O(degree) | Most cases, sparse graphs |
| Edge List | O(E) | O(E) | — | MST algorithms |
Most important sentence for interviews:
“For most graph problems, I would use adjacency list representation because it is space-efficient and works well for both sparse and moderately dense graphs.”
Would you like to continue with any specific graph-related topic next?
Very common follow-up topics:
- DFS & BFS implementation on adjacency list
- How to represent weighted graph
- Directed vs Undirected representation differences
- Cycle detection using adjacency list
- Shortest path algorithms (BFS, Dijkstra) with adjacency list
- Adjacency matrix vs list – when interviewers ask to choose
Just tell me which one you want — I’ll explain it in the same detailed, step-by-step, teacher style with clear examples and visuals! 😊
