Representing Graphs

Nodes and edges

A graph is a set of vertices (nodes) connected by edges. Graphs can be directed (one-way links, such as follows or dependencies) or undirected (friendships, roads), weighted (distances, costs, latencies) or unweighted, and cyclic or acyclic (a DAG, directed acyclic graph, models dependencies and build orders). Representations trade space for speed. An adjacency list maps each vertex to its neighbours, in Python a dict[str, list[str]] or defaultdict(set); it uses O(V + E) space and is best for sparse graphs, which most real graphs are. An adjacency matrix is a V × V table where cell [u][v] holds the edge weight; checking an edge is O(1) but space is O(V²), suitable for dense graphs or small fixed vertex sets (NumPy arrays make it efficient). An edge list of (u, v, weight) tuples suits algorithms that process edges globally, such as Kruskal's minimum spanning tree. For serious graph work, NetworkX offers a rich, pure-Python library, and igraph or rustworkx are faster for large graphs.

Three graph representations

The same small graph as an adjacency list, an adjacency matrix and an edge list.

Building graphs from data

An undirected weighted adjacency list, a directed dependency graph and a matrix.

from collections import defaultdict

roads = [("Pune", "Mumbai", 150), ("Pune", "Nashik", 210), ("Mumbai", "Nashik", 170), ("Nashik", "Indore", 410)]

# undirected, weighted adjacency list
graph: dict[str, dict[str, int]] = defaultdict(dict)
for a, b, km in roads:
    graph[a][b] = km
    graph[b][a] = km
print(graph["Nashik"])                  # {'Pune': 210, 'Mumbai': 170, 'Indore': 410}
print("Indore" in graph["Pune"])        # False: no direct road

# directed graph: course prerequisites
prereqs = {
    "python-basics": [],
    "data-structures": ["python-basics"],
    "algorithms": ["data-structures"],
    "web-apis": ["python-basics"],
}
dependents = defaultdict(list)          # reverse edges
for course, needs in prereqs.items():
    for need in needs:
        dependents[need].append(course)
print(dependents["python-basics"])      # ['data-structures', 'web-apis']

# adjacency matrix for a small, dense graph
cities = sorted(graph)
index = {c: i for i, c in enumerate(cities)}
matrix = [[0] * len(cities) for _ in cities]
for a, b, km in roads:
    matrix[index[a]][index[b]] = matrix[index[b]][index[a]] = km
print(cities)
print(matrix[index["Pune"]])            # distances from Pune in city order

Default to adjacency lists

Most real graphs (social networks, road maps, dependency graphs) are sparse: each vertex connects to a few others. An adjacency list stores only existing edges, while a matrix wastes space on all the zeros.

त्वरित जाँच: Which representation uses O(V + E) space and suits sparse graphs?

• Adjacency matrix
• A single list of vertices
• Adjacency list
• A V by V NumPy array