Graph Representation

What is a graph?

A graph is a set of vertices (nodes) connected by edges. Graphs model roads between cities, friendships, web links, computer networks, course prerequisites — anything with connections.

• Undirected: an edge works both ways (friendship).
• Directed: an edge has a direction, A → B (following someone on Instagram).
• Weighted: each edge carries a number such as distance or cost.

A drawing is great for humans, but a computer needs a data structure. There are two classic choices, and the 3D model shows both for the same graph.

1. Adjacency matrix

A V × V grid where matrix[u][v] = 1 if there is an edge from u to v, otherwise 0. For weighted graphs, store the weight instead of 1 (and ∞ or 0 for “no edge”).

     A  B  C  D
A  [ 0  1  1  0 ]
B  [ 1  0  0  1 ]
C  [ 1  0  0  1 ]
D  [ 0  1  1  0 ]

• ✅ Checking “is there an edge u–v?” is O(1).
• ✅ Simple, great for dense graphs and algorithms like Floyd–Warshall.
• ❌ Always uses V² memory, even if there are few edges.
• ❌ Listing u’s neighbours means scanning a whole row: O(V).

For an undirected graph the matrix is symmetric across the diagonal.

2. Adjacency list

Each vertex keeps a list of its neighbours:

A → B, C
B → A, D
C → A, D
D → B, C

• ✅ Uses only O(V + E) memory.
• ✅ Visiting neighbours costs O(degree) — perfect for BFS and DFS and Dijkstra.
• ❌ Checking a specific edge u–v means scanning u’s list: O(degree of u).

Which one should I use?

Most real graphs are sparse, so adjacency lists are the default.

Code

V = 6
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]

# Adjacency matrix
matrix = [[0] * V for _ in range(V)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1          # undirected

# Adjacency list
adj = [[] for _ in range(V)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)          # undirected

print(matrix[0][2] == 1)      # O(1) edge check → True
print(adj[3])                 # neighbours of 3 → [1, 2, 4]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 6;
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,3},{2,3},{3,4},{4,5}};

    vector<vector<int>> matrix(V, vector<int>(V, 0));   // O(V^2) memory
    vector<vector<int>> adj(V);                         // O(V + E) memory
    for (auto [u, v] : edges) {
        matrix[u][v] = matrix[v][u] = 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int v : adj[3]) cout << v << " ";              // 1 2 4
}

Other representations

• Edge list: just a list of (u, v, weight) triples — handy for Kruskal’s algorithm, which sorts edges.
• Incidence matrix: V × E grid, mostly used in theory.
• Compressed sparse row (CSR): a memory-efficient adjacency list used for huge graphs.

Common mistakes

• Forgetting to add both directions for an undirected graph.
• Using a matrix for 100,000 vertices — that’s 10 billion cells!
• Confusing indexes and labels (A, B, C…); keep a mapping from names to numbers.