Graph Representations

A graph G = (V, E) contains vertices and edges. Edges may be directed or undirected, weighted or unweighted. A path is a sequence of adjacent vertices; a simple path repeats no vertex.

Adjacency list

Store the outgoing neighbors of each vertex. Space is Θ(V + E) and iterating the neighbors of v costs Θ(out-degree(v)).

static List<List<Integer>> directedGraph(int vertices, int[][] edges) {
    List<List<Integer>> adjacency = new ArrayList<>(vertices);
    for (int v = 0; v < vertices; v++) adjacency.add(new ArrayList<>());
    for (int[] edge : edges) adjacency.get(edge[0]).add(edge[1]);
    return adjacency;
}

For an undirected graph, add both orientations of every edge. Self-loops and parallel edges are legal only when the chosen graph model permits them.

Adjacency matrix

A V × V matrix uses Θ(V²) space. Edge-existence queries are Θ(1), while enumerating a vertex's neighbors takes Θ(V). It is appropriate for dense graphs or matrix-based algorithms.

Edge list

An edge list stores each edge directly and uses Θ(E) space. It is convenient when algorithms primarily sort or scan edges, as Kruskal's algorithm does.

Choosing a representation

Need	Common choice
Sparse graph traversal	Adjacency list
Constant-time edge test in a dense graph	Adjacency matrix
Sort all edges	Edge list
Multiple edge properties	Edge objects or compact parallel arrays

Representation changes constants and available operations but does not change the mathematical graph. Always state whether V means a count or a set and whether two stored orientations represent one undirected edge.

Exercises

1. Represent the same directed graph in all three forms.
2. Derive the sum of degrees for an undirected graph.
3. Explain how isolated vertices appear in each representation.