Graph Data
Structures

A graph G = (V, E) consists of a set of vertices (nodes) and a set of edges (links) connecting them.

5 vertices, 6 edges, connected graph

A weighted graph assigns a numeric value (weight, cost, capacity) to each edge. Weights represent distance, latency, bandwidth, probability, or any domain metric.

Where weights matter

• Shortest path -- Dijkstra, Bellman-Ford, A* all require edge weights
• Minimum spanning tree -- Kruskal, Prim select lowest-weight edges
• Network flow -- edge weights represent capacities
• Negative weights -- Bellman-Ford handles them; Dijkstra does not

An unweighted graph is a weighted graph where every edge has weight 1.

For a graph with n vertices, allocate an n x n matrix M. M[i][j] = 1 if edge (i, j) exists, 0 otherwise. For weighted graphs, store the weight.

Vertices: A=0  B=1  C=2  D=3

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

Characteristics

Best for dense graphs where |E| approaches |V|2. Wastes memory on sparse graphs.

Each vertex stores a list (array, linked list, or hash set) of its neighbours. The most common representation in practice.

A -> [B, C]
B -> [A, D]
C -> [A, D]
D -> [B, C]

Default choice for most graph algorithms. BFS and DFS run in O(V + E) -- optimal.

Characteristics

Graph:  0->[1,3]  1->[2]  2->[3]  3->[]

row_ptr: [0, 2, 3, 4, 4]
col_idx: [1, 3, 2, 3]
values:  [1, 1, 1, 1]

Characteristics

• Space: O(V + E) with minimal overhead
• Neighbour iteration: contiguous memory scan -- cache-friendly
• Edge lookup: binary search within row -- O(log degree)
• Weakness: static -- inserting edges requires full rebuild

Standard format for high-performance graph libraries (Boost Graph, SuiteSparse, cuGraph) and GPU graph processing. CSC (Compressed Sparse Column) enables efficient in-neighbour access.

Examples

Neighbour function pattern

def neighbours(state):
    for move in legal_moves(state):
        yield apply(move, state)

# BFS with implicit graph
from collections import deque
def bfs(start, goal):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        if node == goal:
            return True
        for nbr in neighbours(node):
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return False

If your graph has more than ~10⁸ vertices, implicit representation combined with BFS, DFS, or A* is the only practical option.

A graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. No edge within the same set.

Detection: BFS 2-colouring

1. Pick any unvisited vertex, colour it red
2. Colour all neighbours blue
3. Colour their uncoloured neighbours red
4. If a neighbour already has the same colour -- not bipartite
5. Repeat for disconnected components

Time complexity: O(V + E). A graph is bipartite iff it contains no odd-length cycle.

Applications

• Job matching -- workers to tasks (Hungarian algorithm)
• Recommendations -- users to items
• Scheduling -- time slots to courses

A directed acyclic graph is a directed graph with no cycles. Every DAG has at least one topological ordering.

Key properties

• At least one vertex with in-degree 0 (source) and one with out-degree 0 (sink)
• Longest path is finite and computable in O(V + E)
• Number of paths between two vertices can be exponential
• Transitive closure and reduction are well-defined

Cycle detection

Run DFS and check for back edges -- an edge to a vertex currently on the recursion stack. If found, the graph has a cycle and is not a DAG.

Why DAGs matter

Topological order: A, B, C, D, E

Native graph databases

Store vertices and edges as first-class objects with index-free adjacency -- each node physically points to its neighbours.

Relational graph storage

CREATE TABLE vertices (
  id    INTEGER PRIMARY KEY,
  label VARCHAR(64),
  props JSONB
);
CREATE TABLE edges (
  src    INTEGER REFERENCES vertices(id),
  dst    INTEGER REFERENCES vertices(id),
  label  VARCHAR(64),
  weight FLOAT,
  PRIMARY KEY (src, dst, label)
);

Trade-offs

Use a native graph DB when your core access pattern is multi-hop traversal. Use relational when you also need joins, aggregation, and mature tooling.

Key takeaways

• A graph G = (V, E) is the most flexible data structure -- trees, lists, and matrices are all special cases
• Adjacency list is the default choice -- O(V + E) space, optimal traversal
• Adjacency matrix excels at dense graphs and matrix algebra
• CSR format is essential for HPC and GPU graph processing
• DAGs underpin build systems, data pipelines, version control, and scheduling
• Property graph DBs and RDF triple stores serve different persistence needs
• Choose representation based on density, mutation frequency, and algorithm requirements

Recommended reading