Graph models and adjacency representations

A graph G=(V,E) represents entities and relations. Specify directedness, weights, parallel edges, self-loops and disconnected components. An undirected edge is typically represented twice in adjacency lists; do not confuse stored entries with E.

Matrices need V² cells, constant edge lookup and O(V) neighbour scans. Lists need O(V+E) space and degree-based scans, while a plain-list edge lookup costs O(degree). Edge lists suit Kruskal; CSR improves locality on large graphs.

Labels need not be dense array indices. Map labels to IDs or use dictionaries. Specify whether traversal reads an immutable snapshot; adjacency mutation can invalidate iteration. Distinguish vertices reachable from one root from processing all V.

def undirected_graph(vertices, edges):
    g = {v: [] for v in vertices}
    for a, b in edges:
        g[a].append(b); g[b].append(a)
    return g
assert undirected_graph("ABC", [("A","B"),("B","C")])["B"] == ["A","C"]