Graph Representation
Adjacency List
An adjacency list stores, for each vertex, a list of the vertices it's directly connected to — this is compact and efficient for sparse graphs (where most vertices only connect to a few others), which is the most common case in practice.
Example: Adjacency List
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> adj(4);
adj[0].push_back(1); adj[0].push_back(2);
adj[1].push_back(0);
for (int v : adj[0]) cout << v << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 4; i++) adj.add(new ArrayList<>());
adj.get(0).add(1); adj.get(0).add(2);
System.out.println(adj.get(0));
}
}adj = [[] for _ in range(4)]
adj[0].extend([1, 2])
adj[1].append(0)
print(adj[0])#include <stdio.h>
int main() {
int adj[4][4] = {0}, adjCount[4] = {0};
adj[0][adjCount[0]++] = 1;
adj[0][adjCount[0]++] = 2;
for (int i = 0; i < adjCount[0]; i++) printf("%d ", adj[0][i]);
return 0;
}Login to try C/C++/Java code in the editor
Adjacency Matrix
An adjacency matrix uses a 2D grid where rows and columns represent vertices, and the cell at (i, j) indicates whether an edge exists between vertex i and vertex j — this makes checking whether a specific edge exists an instant O(1) lookup.
Example: Adjacency Matrix
#include <iostream>
using namespace std;
int main() {
int matrix[4][4] = {0};
matrix[0][1] = 1; matrix[1][0] = 1;
cout << "Edge (0,1) exists: " << (matrix[0][1] ? "yes" : "no");
return 0;
}public class Main {
public static void main(String[] args) {
int[][] matrix = new int[4][4];
matrix[0][1] = 1; matrix[1][0] = 1;
System.out.println("Edge (0,1) exists: " + (matrix[0][1] == 1 ? "yes" : "no"));
}
}matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
print("Edge (0,1) exists:", "yes" if matrix[0][1] else "no")#include <stdio.h>
int main() {
int matrix[4][4] = {0};
matrix[0][1] = 1; matrix[1][0] = 1;
printf("Edge (0,1) exists: %s", matrix[0][1] ? "yes" : "no");
return 0;
}Login to try C/C++/Java code in the editor
Edge List
An edge list simply stores every edge as a pair (or a triple, if it carries a weight) without organizing them by vertex at all — this is the simplest representation to build and is often used as an intermediate format before converting to a list or matrix.
Example: Edge List
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> edges = {{0,1,4}, {1,2,7}, {0,2,3}};
for (auto& e : edges) cout << e[0] << "-" << e[1] << "(w=" << e[2] << ") ";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] edges = {{0,1,4}, {1,2,7}, {0,2,3}};
for (int[] e : edges) System.out.print(e[0] + "-" + e[1] + "(w=" + e[2] + ") ");
}
}edges = [(0,1,4), (1,2,7), (0,2,3)]
for u, v, w in edges:
print(f"{u}-{v}(w={w})", end=" ")#include <stdio.h>
int main() {
int edges[3][3] = {{0,1,4}, {1,2,7}, {0,2,3}};
for (int i = 0; i < 3; i++) printf("%d-%d(w=%d) ", edges[i][0], edges[i][1], edges[i][2]);
return 0;
}Login to try C/C++/Java code in the editor
Choosing a Representation
The right representation depends on the graph's density and what operations the algorithm needs most: adjacency lists suit sparse graphs and neighbor-iteration-heavy algorithms, while adjacency matrices suit dense graphs or algorithms that frequently check specific edges.
Example: Choosing a Representation
#include <iostream>
using namespace std;
int main() {
cout << "Sparse graph + neighbor iteration -> adjacency list; dense graph + edge lookup -> matrix";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Sparse graph + neighbor iteration -> adjacency list; dense graph + edge lookup -> matrix");
}
}print("Sparse graph + neighbor iteration -> adjacency list; dense graph + edge lookup -> matrix")#include <stdio.h>
int main() {
printf("Sparse graph + neighbor iteration -> adjacency list; dense graph + edge lookup -> matrix");
return 0;
}Login to try C/C++/Java code in the editor
Complexity Idea
Memory usage differs sharply between representations: an adjacency matrix always uses O(V²) space regardless of how many edges actually exist, while an adjacency list uses O(V + E) space, which is far smaller for sparse graphs with relatively few edges.
Example: Complexity Idea
#include <iostream>
using namespace std;
int main() {
int V = 1000, E = 3000;
cout << "Matrix: O(V^2)=" << V*V << " cells; List: O(V+E)=" << V+E << " entries";
return 0;
}public class Main {
public static void main(String[] args) {
int V = 1000, E = 3000;
System.out.println("Matrix: O(V^2)=" + (V*V) + " cells; List: O(V+E)=" + (V+E) + " entries");
}
}V, E = 1000, 3000
print(f"Matrix: O(V^2)={V*V} cells; List: O(V+E)={V+E} entries")#include <stdio.h>
int main() {
int V = 1000, E = 3000;
printf("Matrix: O(V^2)=%d cells; List: O(V+E)=%d entries", V*V, V+E);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: