Graph Representation

A graph is a set of vertices (nodes) connected by edges. Trees, which you've already seen, are actually a restricted special case of graphs (no cycles, one path between any two nodes). Graphs drop those restrictions — any node can connect to any other, cycles are allowed, and a node can have any number of connections. Before you can run any graph algorithm, you need to decide how to actually store one in memory — that's what this lesson covers.

Types of Graphs

Example Graph

We'll represent this small undirected, weighted graph with 4 vertices both ways:

    A --- 4 --- B
    |           |
    2           3
    |           |
    C --- 1 --- D

Edges: A-B (4), A-C (2), B-D (3), C-D (1). Using integer indices A=0, B=1, C=2, D=3.

Adjacency Matrix

A 2D array matrix[V][V] where matrix[i][j] holds the edge weight between vertex i and j (or 0 / a sentinel value if there's no edge). For an undirected graph, the matrix is symmetric.

// 4 vertices: A=0, B=1, C=2, D=3. 0 means "no edge".
int[][] matrix = new int[4][4];

void addEdge(int[][] matrix, int u, int v, int weight) {
    matrix[u][v] = weight;
    matrix[v][u] = weight;  // undirected -> set both directions
}

addEdge(matrix, 0, 1, 4);  // A-B
addEdge(matrix, 0, 2, 2);  // A-C
addEdge(matrix, 1, 3, 3);  // B-D
addEdge(matrix, 2, 3, 1);  // C-D

// Is there an edge between A(0) and C(2)? One array lookup:
boolean connected = matrix[0][2] != 0;  // true, weight 2

Time complexity: O(1) to check if an edge exists or read its weight — direct array indexing. Space complexity: O(V²) — the matrix allocates a slot for every possible pair of vertices, whether or not an edge exists between them.

Adjacency List

Instead of a full grid, each vertex keeps a list of only its actual neighbors (and, for a weighted graph, the weight to each). This is dramatically smaller for sparse graphs — most real-world graphs (social networks, road maps, dependency graphs) have far fewer edges than the V² a matrix would reserve space for.

class Edge {
    int to, weight;
    Edge(int to, int weight) { this.to = to; this.weight = weight; }
}

// One list per vertex, holding only its actual neighbors.
List<List<Edge>> adjList = new ArrayList<>();
for (int i = 0; i < 4; i++) adjList.add(new ArrayList<>());

void addEdge(List<List<Edge>> adj, int u, int v, int weight) {
    adj.get(u).add(new Edge(v, weight));
    adj.get(v).add(new Edge(u, weight));  // undirected -> add both directions
}

addEdge(adjList, 0, 1, 4);  // A-B
addEdge(adjList, 0, 2, 2);  // A-C
addEdge(adjList, 1, 3, 3);  // B-D
addEdge(adjList, 2, 3, 1);  // C-D

// Neighbors of A(0): iterate its list directly.
for (Edge e : adjList.get(0)) {
    System.out.println("A -> " + e.to + " (weight " + e.weight + ")");
}
// A -> 1 (weight 4)
// A -> 2 (weight 2)

Time complexity: O(degree(v)) to list vertex v's neighbors — you only touch edges that actually exist, versus scanning a full row of V in a matrix. Checking a specific edge is O(degree(v)) worst case (scanning the list) rather than O(1). Space complexity: O(V + E) — one list header per vertex plus one entry per edge (two entries per undirected edge), far smaller than V² when E is much less than V².

Which One Should You Pick?