# Representing Graphs — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/g-repr

> Model graphs with adjacency lists, adjacency matrices and edge lists.

## 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.

![A small graph of four connected circles on the left, with three panels on the right: a list of neighbour lists, a 4 by 4 grid of numbers and a column of pairs.](assets/figures/data-structures-python/section-6-map.svg) — Figure 6.1 — Adjacency list, matrix and edge list.

## Building graphs from data

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

```python
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.

**Quiz:** Which representation uses O(V + E) space and suits sparse graphs?

- [ ] Adjacency matrix
- [ ] A single list of vertices
- [x] Adjacency list
- [ ] A V by V NumPy array

*Answer:* Adjacency list. Adjacency lists store only the edges that exist.