Representation of Graphs

A graph is a pair G = (V, E) where V is a set of vertices (also called nodes) and E is a set of edges that connect pairs of vertices. Graphs model anything that has things and relationships: roads between cities, friendships between people, dependencies between tasks, links between web pages, pixels in an image.

Two flavors matter most:

• Undirected — an edge {u, v} is a symmetric connection (e.g. a friendship).
• Directed — an edge (u, v) points from u to v and may have no reverse (e.g. a Twitter follow).

Edges can also be weighted (carry a number like distance or cost) or unweighted (just present or absent).

Example — undirected graph with 5 vertices:

Vertices: {1, 2, 3, 4, 5} · Edges: {1-2, 1-3, 1-4, 2-3, 3-4, 3-5}.

Given the same graph, we can store it in (at least) three different ways. Each one trades memory for query speed.

1. Adjacency matrix — a V × V boolean (or weight) matrix A where A[u][v] = 1 if there is an edge from u to v.

2. Adjacency list — for each vertex u, a list of vertices reachable from u in one edge.

3. Edge list — a flat list of edges (u, v[, w]), with no per-vertex index.

The right choice depends on density (E vs. V²) and on which queries you run most:

For the 5-vertex undirected graph above, the adjacency matrix is symmetric (A[u][v] = A[v][u]):

Reading row 3 across, the 1s sit in columns 1, 2, 4, 5 — exactly the neighbors of vertex 3.

When to use it: the graph is dense (close to V² edges), or you need O(1) hasEdge(u, v) lookups (e.g. Floyd–Warshall, dense max-flow).

When not to use it: sparse graphs with V = 10⁵ — a 10⁵×10⁵ matrix holds 10¹⁰ entries, which is out of the question both in memory and time.

For the same graph, the adjacency list stores only the existing edges:

Total entries = 2·|E| = 12 for an undirected graph (each edge appears twice — once at each endpoint). For a sparse graph this is dramatically smaller than a matrix.

This is the default representation for almost every BFS, DFS, Dijkstra, Bellman–Ford, Kruskal, and Prim implementation you will write. Pretty much every algorithm that scans neighbors of a vertex benefits from O(deg(u)) iteration.

Weighted version: store (neighbor, weight) pairs instead of just neighbors:

An edge list is just an array of edges. Each entry is (u, v) for unweighted graphs or (u, v, w) for weighted ones.

It is the natural format when the algorithm processes edges as a whole rather than walking neighbors of a vertex — Kruskal's MST is the canonical example: sort edges by weight, then scan them in order. Reading the input as an edge list and converting to an adjacency list when needed is a common pattern.

Suppose the input is the number of vertices n = 5, the number of edges m = 6, and a list of edges. We build the adjacency list in m steps.

Input edges: (1,2), (1,3), (1,4), (2,3), (3,4), (3,5)

For a directed graph, drop the second push — only add v to u's list, not the other way around.

Building any representation is a single pass over the input edges — the only decision is where each edge gets recorded. The pseudocode covers both the adjacency list and the adjacency matrix; the C++ tab is a complete program that reads n, m, and the edge list, builds all three representations, and prints the adjacency list.

Rule of thumb: if V ≤ 1000, either representation is fine. For larger V, prefer the adjacency list unless the graph is genuinely dense (E close to V²/2).