Graph representations: adjacency lists

A graph consists of vertices (nodes) and edges (connections). Unlike trees, graphs may contain cycles and disconnected components. Edges may be directed or undirected, and may carry weights such as distance or cost. Choose a representation that matches the operations you need.

Adjacency list versus matrix

In an adjacency list, each vertex stores its neighboring vertices. A graph with V vertices and E edges occupies O(V + E) storage for the lists, assuming standard indexing and no extra metadata. In an adjacency matrix, a V-by-V table records possible edges and uses O(V²) storage even when few connections exist. Matrix edge membership is O(1) lookup; scanning a vertex’s neighbors typically costs O(V) rather than its degree.

Small example

For an undirected graph with edges A-B, A-D and B-C, the lists are A: [B, D], B: [A, C], C: [B], D: [A]. Each undirected edge appears in two adjacency lists. A directed edge A → B would appear only in A’s outgoing list unless a separate reverse index is maintained.

C#

C# | AdjacencyList.cs

// Undirected graph: 0-A, 1-B, 2-C, 3-D
var adjacency = new List<int>[]
{
    new() { 1, 3 }, // A
    new() { 0, 2 }, // B
    new() { 1 },    // C
    new() { 0 }     // D
};

C++

C++ | AdjacencyList.cpp

#include <vector>
// Undirected graph: 0-A, 1-B, 2-C, 3-D
std::vector<std::vector<int>> adjacency = {
    {1, 3}, // A
    {0, 2}, // B
    {1},    // C
    {0}     // D
};

Traversal considerations

BFS and DFS need access to each vertex’s neighbors; adjacency lists let the search touch each reachable edge once or twice under the representation. For disconnected graphs, starting at one vertex does not traverse the entire graph. To cover all components, run the search again from each unvisited vertex. Decide how duplicate edges, self-loops and invalid vertex identifiers are handled before processing untrusted input.

Practice: Draw a four-vertex cycle, write its adjacency lists, and explain why a naive recursive search without a visited set would never terminate.

Continue with BFS and DFS.