DSA Tutorial
🔍
Graph Representation
Why Representation Matters
The graph representation you choose determines the time and space complexity of every operation — BFS, DFS, shortest path, neighbour lookup, edge check. There is no universally best choice: each representation has a different trade-off.
REFERENCE GRAPH for all examples:
Undirected weighted graph:
0 ──4── 1 ──8── 2
| | |
11 7 2──5
| | |
7 ──9── 6 3──4
/ \
2 6
/ \
8 4
Simplified for clarity — use this graph:
0 ───4─── 1
│ │ \
│8 7 \6
│ │ \
7 ──9─── 6 ─2── 5
\
3
Let's use a cleaner 5-vertex example:
Vertices: {0, 1, 2, 3, 4}
Edges (undirected, weighted):
(0,1,4) (0,2,1) (1,2,2)
(1,3,5) (2,4,8) (3,4,3)
0 ──4── 1
│ │ \
1 2 5
│ │ \
2 ──8── 4 ──3─ 3
This 5-vertex, 6-edge graph is used for ALL representations below.
Representation 1: Adjacency Matrix
Store a V × V 2D array. matrix[u][v] = weight (or 1 for unweighted) if edge (u,v) exists, 0 otherwise.
Graph: 0─4─1, 0─1─2, 1─2─2, 1─5─3, 2─8─4, 3─4─3
Weighted adjacency matrix (undirected → symmetric):
0 1 2 3 4
0 [ 0, 4, 1, 0, 0 ]
1 [ 4, 0, 2, 5, 0 ]
2 [ 1, 2, 0, 0, 8 ]
3 [ 0, 5, 0, 0, 3 ]
4 [ 0, 0, 8, 3, 0 ]
matrix[0][1] = 4 ← edge (0,1) has weight 4
matrix[1][0] = 4 ← symmetric (undirected)
matrix[0][3] = 0 ← no edge between 0 and 3
UNWEIGHTED: replace weights with 1 (edge exists) / 0 (no edge)
DIRECTED: matrix is NOT symmetric (matrix[u][v] ≠ matrix[v][u] in general)
Java
1public class AdjacencyMatrix {
2
3 private int[][] matrix;
4 private int vertices;
5 private boolean directed;
6
7 public AdjacencyMatrix(int vertices, boolean directed) {
8 this.vertices = vertices;
9 this.directed = directed;
10 this.matrix = new int[vertices][vertices];
11 }
12
13 // Add edge — O(1)
14 public void addEdge(int u, int v, int weight) {
15 matrix[u][v] = weight;
16 if (!directed) matrix[v][u] = weight; // Undirected: both directions
17 }
18
19 // Remove edge — O(1)
20 public void removeEdge(int u, int v) {
21 matrix[u][v] = 0;
22 if (!directed) matrix[v][u] = 0;
23 }
24
25 // Check if edge exists — O(1)
26 public boolean hasEdge(int u, int v) { return matrix[u][v] != 0; }
27
28 // Get edge weight — O(1)
29 public int getWeight(int u, int v) { return matrix[u][v]; }
30
31 // Get all neighbours of vertex u — O(V)
32 public java.util.List<Integer> neighbours(int u) {
33 java.util.List<Integer> result = new java.util.ArrayList<>();
34 for (int v = 0; v < vertices; v++) {
35 if (matrix[u][v] != 0) result.add(v);
36 }
37 return result;
38 }
39
40 // Print matrix
41 public void print() {
42 System.out.print(" ");
43 for (int i = 0; i < vertices; i++) System.out.printf("%3d", i);
44 System.out.println();
45 for (int u = 0; u < vertices; u++) {
46 System.out.printf("%3d ", u);
47 for (int v = 0; v < vertices; v++) System.out.printf("%3d", matrix[u][v]);
48 System.out.println();
49 }
50 }
51
52 public static void main(String[] args) {
53 AdjacencyMatrix g = new AdjacencyMatrix(5, false); // Undirected
54 g.addEdge(0, 1, 4); g.addEdge(0, 2, 1);
55 g.addEdge(1, 2, 2); g.addEdge(1, 3, 5);
56 g.addEdge(2, 4, 8); g.addEdge(3, 4, 3);
57
58 g.print();
59
60 System.out.println("Has edge (0,1): " + g.hasEdge(0, 1)); // true
61 System.out.println("Has edge (0,3): " + g.hasEdge(0, 3)); // false
62 System.out.println("Weight (1,3): " + g.getWeight(1, 3)); // 5
63 System.out.println("Neighbours(1): " + g.neighbours(1)); // [0,2,3]
64 }
65}Output (matrix):
0 1 2 3 4
0 0 4 1 0 0
1 4 0 2 5 0
2 1 2 0 0 8
3 0 5 0 0 3
4 0 0 8 3 0
Has edge (0,1): true
Has edge (0,3): false
Weight (1,3): 5
Neighbours(1): [0, 2, 3]
Representation 2: Adjacency List
Store an array of lists. adj[u] holds all vertices (and optionally weights) directly connected to u.
Graph: 0─4─1, 0─1─2, 1─2─2, 1─5─3, 2─8─4, 3─4─3 Adjacency list (undirected, weighted): 0: [(1,4), (2,1)] 1: [(0,4), (2,2), (3,5)] 2: [(0,1), (1,2), (4,8)] 3: [(1,5), (4,3)] 4: [(2,8), (3,3)] (neighbour, weight) pairs Each edge (u,v,w) creates TWO entries for undirected: u's list: (v, w) v's list: (u, w) Total entries: V + 2E = 5 + 12 = 17 entries (much less than 25 for matrix) UNWEIGHTED version: store just neighbour IDs 0: [1, 2] 1: [0, 2, 3] ...
Java
1import java.util.*;
2
3public class AdjacencyList {
4
5 // Inner class for weighted edge
6 static class Edge {
7 int dest, weight;
8 Edge(int dest, int weight) { this.dest = dest; this.weight = weight; }
9 @Override public String toString() { return "(" + dest + "," + weight + ")"; }
10 }
11
12 private List<List<Edge>> adj;
13 private int vertices;
14 private boolean directed;
15
16 public AdjacencyList(int vertices, boolean directed) {
17 this.vertices = vertices;
18 this.directed = directed;
19 adj = new ArrayList<>();
20 for (int i = 0; i < vertices; i++) adj.add(new ArrayList<>());
21 }
22
23 // Add edge — O(1)
24 public void addEdge(int u, int v, int weight) {
25 adj.get(u).add(new Edge(v, weight));
26 if (!directed) adj.get(v).add(new Edge(u, weight));
27 }
28
29 // Remove edge — O(degree(u))
30 public void removeEdge(int u, int v) {
31 adj.get(u).removeIf(e -> e.dest == v);
32 if (!directed) adj.get(v).removeIf(e -> e.dest == u);
33 }
34
35 // Check if edge exists — O(degree(u))
36 public boolean hasEdge(int u, int v) {
37 return adj.get(u).stream().anyMatch(e -> e.dest == v);
38 }
39
40 // Get edge weight — O(degree(u))
41 public int getWeight(int u, int v) {
42 return adj.get(u).stream()
43 .filter(e -> e.dest == v)
44 .mapToInt(e -> e.weight)
45 .findFirst()
46 .orElse(0);
47 }
48
49 // Get all neighbours — O(1) to get list, O(degree) to iterate
50 public List<Edge> neighbours(int u) { return adj.get(u); }
51
52 // Get degree of vertex u
53 public int degree(int u) { return adj.get(u).size(); }
54
55 // Print adjacency list
56 public void print() {
57 for (int u = 0; u < vertices; u++) {
58 System.out.print(u + ": " + adj.get(u));
59 System.out.println();
60 }
61 }
62
63 public static void main(String[] args) {
64 AdjacencyList g = new AdjacencyList(5, false); // Undirected
65 g.addEdge(0, 1, 4); g.addEdge(0, 2, 1);
66 g.addEdge(1, 2, 2); g.addEdge(1, 3, 5);
67 g.addEdge(2, 4, 8); g.addEdge(3, 4, 3);
68
69 g.print();
70
71 System.out.println("Has edge (0,1): " + g.hasEdge(0, 1)); // true
72 System.out.println("Has edge (0,3): " + g.hasEdge(0, 3)); // false
73 System.out.println("Weight (1,3): " + g.getWeight(1, 3)); // 5
74 System.out.println("Degree(1): " + g.degree(1)); // 3
75 System.out.println("Neighbours(2): " + g.neighbours(2)); // [(0,1),(1,2),(4,8)]
76
77 // DIRECTED graph example
78 AdjacencyList dg = new AdjacencyList(4, true);
79 dg.addEdge(0, 1, 1); dg.addEdge(1, 2, 1); dg.addEdge(2, 3, 1); dg.addEdge(3, 0, 1);
80 System.out.println("\nDirected graph:");
81 dg.print();
82 }
83}Output (adjacency list): 0: [(1,4), (2,1)] 1: [(0,4), (2,2), (3,5)] 2: [(0,1), (1,2), (4,8)] 3: [(1,5), (4,3)] 4: [(2,8), (3,3)] Has edge (0,1): true Has edge (0,3): false Weight (1,3): 5 Degree(1): 3 Neighbours(2): [(0,1), (1,2), (4,8)]
Representation 3: Edge List
Store all edges as a flat list of (source, destination, weight) tuples. No vertex-indexed structure.
Graph: 0─4─1, 0─1─2, 1─2─2, 1─5─3, 2─8─4, 3─4─3 Edge list (undirected — each edge stored once): [(0,1,4), (0,2,1), (1,2,2), (1,3,5), (2,4,8), (3,4,3)] UNWEIGHTED version: [(0,1), (0,2), (1,2), (1,3), (2,4), (3,4)] DIRECTED version — only store directed edges, no duplicates. Space: O(E) — just the edge tuples. Perfect for algorithms that iterate over all edges: - Kruskal's MST (sort by weight, process each edge) - Bellman-Ford (relax all edges V-1 times) - Counting edges, finding min/max weight edge
Java
1import java.util.*;
2
3public class EdgeList {
4
5 static class Edge implements Comparable<Edge> {
6 int u, v, weight;
7 Edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; }
8
9 @Override
10 public int compareTo(Edge other) {
11 return Integer.compare(this.weight, other.weight); // Sort by weight
12 }
13
14 @Override
15 public String toString() { return "(" + u + "─" + v + "," + weight + ")"; }
16 }
17
18 private List<Edge> edges = new ArrayList<>();
19 private int vertices;
20 private boolean directed;
21
22 public EdgeList(int vertices, boolean directed) {
23 this.vertices = vertices;
24 this.directed = directed;
25 }
26
27 // Add edge — O(1)
28 public void addEdge(int u, int v, int weight) {
29 edges.add(new Edge(u, v, weight));
30 // For undirected, can add both directions OR just store once
31 // (convention varies by algorithm — Kruskal typically stores once)
32 }
33
34 // Check if edge exists — O(E)
35 public boolean hasEdge(int u, int v) {
36 return edges.stream().anyMatch(e ->
37 (e.u == u && e.v == v) ||
38 (!directed && e.u == v && e.v == u));
39 }
40
41 // Get edge weight — O(E)
42 public int getWeight(int u, int v) {
43 return edges.stream()
44 .filter(e -> (e.u == u && e.v == v) ||
45 (!directed && e.u == v && e.v == u))
46 .mapToInt(e -> e.weight)
47 .findFirst()
48 .orElse(0);
49 }
50
51 // Sort edges by weight — O(E log E) — used by Kruskal's
52 public void sortByWeight() { Collections.sort(edges); }
53
54 // Get all edges
55 public List<Edge> getEdges() { return edges; }
56
57 public void print() {
58 System.out.println("Edge list: " + edges);
59 System.out.println("Total edges: " + edges.size());
60 }
61
62 public static void main(String[] args) {
63 EdgeList g = new EdgeList(5, false);
64 g.addEdge(0, 1, 4); g.addEdge(0, 2, 1);
65 g.addEdge(1, 2, 2); g.addEdge(1, 3, 5);
66 g.addEdge(2, 4, 8); g.addEdge(3, 4, 3);
67
68 g.print();
69
70 System.out.println("Has (0,1): " + g.hasEdge(0, 1)); // true
71 System.out.println("Has (0,3): " + g.hasEdge(0, 3)); // false
72 System.out.println("Weight (2,4): " + g.getWeight(2, 4)); // 8
73
74 // Sort for Kruskal's MST
75 g.sortByWeight();
76 System.out.println("Sorted: " + g.getEdges());
77 // [(0─2,1), (1─2,2), (3─4,3), (0─1,4), (1─3,5), (2─4,8)]
78 }
79}Output:
Edge list: [(0,1,4),(0,2,1),(1,2,2),(1,3,5),(2,4,8),(3,4,3)]
Total edges: 6
Has (0,1): true
Has (0,3): false
Weight (2,4): 8
Sorted: [(0,2,1),(1,2,2),(3,4,3),(0,1,4),(1,3,5),(2,4,8)]
Converting Between Representations
MATRIX → LIST: O(V²) — must scan all V² cells MATRIX → EDGES: O(V²) — must scan all V² cells LIST → MATRIX: O(V + E) — add each edge into matrix LIST → EDGES: O(V + E) — collect edges from each list EDGES → LIST: O(V + E) — add each edge to appropriate list EDGES → MATRIX: O(V + E) — add each edge into matrix WHY MATRIX → LIST IS O(V²): Even if the graph has only E=V edges, you must check all V² matrix cells to find the non-zero entries. You cannot know which cells are non-zero without looking at each one.
Java
1import java.util.*;
2
3public class ConvertRepresentations {
4
5 // Adjacency Matrix → Adjacency List — O(V²)
6 public static List<List<int[]>> matrixToList(int[][] matrix) {
7 int V = matrix.length;
8 List<List<int[]>> adj = new ArrayList<>();
9 for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
10
11 for (int u = 0; u < V; u++)
12 for (int v = 0; v < V; v++)
13 if (matrix[u][v] != 0)
14 adj.get(u).add(new int[]{v, matrix[u][v]});
15
16 return adj;
17 }
18
19 // Adjacency List → Adjacency Matrix — O(V + E)
20 public static int[][] listToMatrix(List<List<int[]>> adj) {
21 int V = adj.size();
22 int[][] matrix = new int[V][V];
23 for (int u = 0; u < V; u++)
24 for (int[] edge : adj.get(u))
25 matrix[u][edge[0]] = edge[1];
26 return matrix;
27 }
28
29 // Adjacency List → Edge List — O(V + E)
30 public static List<int[]> listToEdges(List<List<int[]>> adj, boolean directed) {
31 List<int[]> edges = new ArrayList<>();
32 for (int u = 0; u < adj.size(); u++)
33 for (int[] edge : adj.get(u)) {
34 int v = edge[0], w = edge[1];
35 if (directed || u < v) // Avoid duplicates for undirected
36 edges.add(new int[]{u, v, w});
37 }
38 return edges;
39 }
40
41 // Edge List → Adjacency List — O(V + E)
42 public static List<List<int[]>> edgesToList(int V, List<int[]> edges, boolean directed) {
43 List<List<int[]>> adj = new ArrayList<>();
44 for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
45 for (int[] e : edges) {
46 adj.get(e[0]).add(new int[]{e[1], e[2]});
47 if (!directed) adj.get(e[1]).add(new int[]{e[0], e[2]});
48 }
49 return adj;
50 }
51
52 public static void main(String[] args) {
53 int[][] matrix = {
54 {0, 4, 1, 0, 0},
55 {4, 0, 2, 5, 0},
56 {1, 2, 0, 0, 8},
57 {0, 5, 0, 0, 3},
58 {0, 0, 8, 3, 0}
59 };
60
61 // Matrix → List
62 List<List<int[]>> list = matrixToList(matrix);
63 System.out.println("Matrix → List (vertex 1's neighbours):");
64 for (int[] nb : list.get(1)) System.out.print("(" + nb[0] + "," + nb[1] + ") ");
65 System.out.println(); // (0,4) (2,2) (3,5)
66
67 // List → Edges
68 List<int[]> edges = listToEdges(list, false);
69 System.out.println("List → Edges (count): " + edges.size()); // 6
70 for (int[] e : edges) System.out.print("(" + e[0] + "-" + e[1] + "," + e[2] + ") ");
71 System.out.println();
72 }
73}Output:
Matrix → List:
0: [(1,4),(2,1)]
1: [(0,4),(2,2),(3,5)]
2: [(0,1),(1,2),(4,8)]
3: [(1,5),(4,3)]
4: [(2,8),(3,3)]
List → Edges (6 edges): [(0,1,4),(0,2,1),(1,2,2),(1,3,5),(2,4,8),(3,4,3)]
Edges → List → Matrix (row 1): [4, 0, 2, 5, 0]
Space and Time Comparison
GRAPH: V vertices, E edges Density: sparse = E << V², dense = E ≈ V² OPERATION Adj Matrix Adj List Edge List ────────────────────────────────────────────────────────── Space O(V²) O(V + E) O(E) Add edge O(1) O(1) O(1) Remove edge O(1) O(deg(u)) O(E) Has edge (u,v)? O(1) O(deg(u)) O(E) Get neighbours(v) O(V) O(deg(v)) O(E) Iterate ALL edges O(V²) O(V + E) O(E) Build structure O(V²) O(V + E) O(E) ALGORITHM SUITABILITY: BFS / DFS → Adjacency List (iterate neighbours) Dijkstra's → Adjacency List (iterate neighbours with weights) Bellman-Ford → Edge List (relax all edges V-1 times) Kruskal's MST → Edge List (sort edges by weight) Prim's MST → Adjacency List (iterate neighbours) Floyd-Warshall → Adjacency Matrix (all-pairs: matrix[i][j][k]) Has specific edge? → Adjacency Matrix (O(1) lookup) Dense graph ≥ V²/2 → Adjacency Matrix (space comparable to list) Sparse graph → Adjacency List (memory efficient) RECOMMENDATION: Default choice for most problems → ADJACENCY LIST Use matrix only when: O(1) edge check needed, or dense graph Use edge list only when: algorithm iterates all edges (Kruskal, Bellman-Ford)
When to Use Which Representation
USE ADJACENCY MATRIX when: ✓ Need O(1) edge existence check (e.g., "is u adjacent to v?") ✓ Graph is dense (E ≈ V²) — matrix space is acceptable ✓ Floyd-Warshall all-pairs shortest path (natural matrix DP) ✓ Transitive closure computation ✓ Small graphs where simplicity matters over memory USE ADJACENCY LIST when: ✓ Graph is sparse (most real-world graphs: roads, social, web) ✓ BFS / DFS traversal — iterate all neighbours efficiently ✓ Dijkstra's / Prim's — pick minimum weight neighbour ✓ Memory is a constraint ✓ DEFAULT choice for most graph problems USE EDGE LIST when: ✓ Kruskal's MST — sort edges by weight and process each ✓ Bellman-Ford — relax all edges V-1 times ✓ Need to iterate ALL edges without needing vertex-indexed access ✓ Building a graph from an input list of edges ✓ Storing a graph compactly (O(E) space)
Common Mistakes
Not storing both directions for undirected graphs in adjacency list. When edge (u,v) is undirected, add v to u's list AND add u to v's list. Forgetting the second insertion creates a directed graph implicitly — BFS/DFS from u will reach v but DFS from v won't reach u.
Using adjacency matrix for sparse graphs. For a social network with 1 million users and 10 million friendships: adjacency matrix = 10¹² entries (terabytes of RAM). Adjacency list = ~21 million entries (manageable). Always assess sparsity before choosing matrix.
Integer overflow in matrix indices for large graphs. For V = 100,000 vertices, V² = 10¹⁰ — exceeding 32-bit integer range for flat arrays. Either use long indices, or switch to adjacency list.
Checking edge (u,v) in adjacency list using linear scan when O(1) is needed. Adjacency list gives O(deg(u)) edge check. If O(1) is required, use either adjacency matrix or a hash set for each vertex's neighbour set (HashSet<Integer> instead of List<Integer>).
Edge list duplicates for undirected graphs. Undirected edge (u,v) should be stored ONCE in an edge list (by convention u < v). Storing both (u,v) and (v,u) doubles the edge count and causes problems in algorithms like Kruskal's which process each edge once.
Interview Questions
Q: An interviewer gives you a graph problem. Which representation do you choose?
Default to adjacency list. Ask: Is the graph sparse or dense? For sparse (most common — social networks, road networks, dependency graphs), adjacency list is memory-efficient and gives O(degree) neighbour access which BFS and DFS need. If the problem specifically requires O(1) edge check or describes a dense graph (complete or near-complete), use adjacency matrix. If the algorithm iterates all edges (Kruskal's, Bellman-Ford), build an edge list.
Q: Why is BFS/DFS time complexity written as O(V + E) and not O(V × degree)?
O(V + E) comes from adjacency list representation. BFS visits each vertex once (V operations for dequeue) and iterates each edge exactly once (E operations total across all neighbour lists). With adjacency matrix, BFS is O(V²) — each vertex requires scanning V entries to find its neighbours. So the O(V + E) guarantee specifically assumes adjacency list representation.
Q: How would you represent a multigraph (multiple edges between same vertices)?
Adjacency list handles multigraphs naturally — just add the edge multiple times to the lists, and the list can contain duplicate destinations. Adjacency matrix cannot represent multigraphs with a single integer per cell — you'd need to store edge count or use a matrix of lists. Edge list handles multigraphs trivially — just add multiple (u,v,w) tuples.
Summary
Three representations for a graph with V vertices and E edges:
Adjacency Matrix — O(V²) space, O(1) edge check:
- ›Build: allocate V×V array;
matrix[u][v] = weight - ›Undirected: symmetric (
matrix[u][v] = matrix[v][u]) - ›Best for: dense graphs, O(1) edge lookup, Floyd-Warshall
Adjacency List — O(V + E) space, O(deg) edge check:
- ›Build: array of lists;
adj[u].add((v, weight)) - ›Undirected: add to both lists
- ›Best for: sparse graphs, BFS/DFS, Dijkstra's, Prim's — default choice
Edge List — O(E) space, O(E) edge check:
- ›Build: flat list of (u, v, weight) tuples
- ›Sort by weight for Kruskal's: O(E log E)
- ›Best for: Kruskal's MST, Bellman-Ford, any algorithm iterating all edges
Conversion times:
- ›Matrix → List/Edges: O(V²) — must scan all cells
- ›List → Matrix/Edges: O(V + E)
- ›Edges → List/Matrix: O(V + E)
In the next topic you will explore Graph DFS — depth-first traversal, connected components, cycle detection, and topological sort.
Suggested Quiz
An adjacency list for an undirected graph with V=5 vertices and E=7 edges stores how many total neighbour entries?
1/6