Quick answer: An adjacency list maps each graph node to its neighbors, usually with a dictionary. Lists preserve insertion order and can represent duplicate edges, sets enforce unique neighbors, and nested dictionaries can store weights or other edge data. Add both directions for an undirected edge, then use a queue for BFS or a stack for DFS while tracking visited nodes.
An adjacency list is a graph representation where each node stores the nodes connected to it. In Python, this usually means a dictionary whose keys are nodes and whose values are lists, sets, or dictionaries of neighbors.
Adjacency lists are compact for sparse graphs because they store only existing edges. They are also natural for traversal algorithms such as breadth-first search, depth-first search, shortest paths, and minimum spanning tree algorithms.
Basic adjacency list in Python
For an unweighted graph, a dictionary of lists is the simplest structure. Each key is a node, and each list contains neighboring nodes.
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": [],
}
print(graph["A"])This representation is easy to read and works well for small examples. The Python tutorial section on dictionaries explains the mapping behavior behind this pattern.
Directed vs undirected adjacency lists
In a directed graph, an edge from A to B is stored only under A. In an undirected graph, the edge is stored in both directions.
def add_undirected_edge(graph, left, right):
graph.setdefault(left, []).append(right)
graph.setdefault(right, []).append(left)
graph = {}
add_undirected_edge(graph, "A", "B")
add_undirected_edge(graph, "A", "C")
print(graph)Use a directed list for one-way relationships such as dependencies, routes, or state transitions. Use an undirected list for mutual relationships such as friendships, two-way roads, or simple network connections.
Use sets to avoid duplicate neighbors
If duplicate edges are possible, store neighbors in a set instead of a list. A set keeps each neighbor only once and gives fast membership checks.
graph = {
"A": {"B", "C"},
"B": {"A", "D"},
"C": {"A"},
"D": {"B"},
}
if "C" in graph["A"]:
print("A is connected to C")Lists preserve insertion order and are convenient for examples. Sets are better when you care more about uniqueness and membership tests than neighbor order.
Create an adjacency list with defaultdict
collections.defaultdict makes graph construction cleaner because missing keys create an empty neighbor container automatically.
from collections import defaultdict
graph = defaultdict(list)
edges = [("A", "B"), ("A", "C"), ("B", "D")]
for source, target in edges:
graph.append(target)
print(dict(graph))The official defaultdict documentation covers the container. For nested mapping patterns, see Python Pool’s nested dictionary in Python guide.
Weighted adjacency list
Weighted graphs need to store both the neighbor and the edge weight. A dictionary of dictionaries is a clear representation.
weighted_graph = {
"A": {"B": 4, "C": 2},
"B": {"D": 5},
"C": {"B": 1, "D": 8},
"D": {},
}
print(weighted_graph["A"]["C"])This structure is common in shortest-path code because you can iterate over each neighbor and weight together.
for neighbor, weight in weighted_graph["A"].items():
print(neighbor, weight)For a complete shortest-path implementation, see Python Pool’s Dijkstra’s algorithm in Python. Python’s official heapq documentation is also useful because priority queues are often used with weighted adjacency lists.
BFS with an adjacency list
Breadth-first search works naturally with an adjacency list because each step asks for the current node’s neighbors.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
print(bfs(graph, "A"))Python Pool’s BFS in Python guide covers traversal in more detail. If your algorithm needs a priority queue rather than a FIFO queue, see Python priority queue.
Adjacency list vs adjacency matrix
An adjacency matrix stores a grid of all possible node pairs. That can be useful for dense graphs or matrix-based algorithms, but it uses more space when most pairs are not connected. An adjacency list stores only existing edges, so it is usually better for sparse graphs.
Use an adjacency list when you need to iterate through neighbors quickly. Use a matrix when the graph is small, dense, or when constant-time edge lookup across every possible pair is more important than memory use.
Using graph libraries
For production graph analysis, a library can save time. NetworkX uses graph objects with methods for nodes, edges, neighbors, and many algorithms. The NetworkX Graph reference is a good starting point when your graph grows beyond a few helper functions.
For minimum spanning tree examples, see Python Pool’s Kruskal’s algorithm in Python. For pointer-based data structures, the doubly linked list guide is related but solves a different problem than graph adjacency.
Common mistakes
Forgetting isolated nodes. Add nodes with empty neighbor lists when they have no outgoing edges but still belong to the graph.
Mixing directed and undirected logic. Decide whether edges should be one-way or two-way before building helper functions.
Duplicating edges accidentally. Use sets if repeated inserts are possible and duplicates would break your traversal.
Storing weights inconsistently. For weighted graphs, pick one representation and keep it consistent across every edge.
Conclusion
An adjacency list is the most practical graph representation for many Python programs. Use a dictionary of lists for simple directed graphs, sets for unique neighbors, and dictionaries of dictionaries for weighted edges. This structure keeps graph code readable and works well with BFS, Dijkstra’s algorithm, and many other graph algorithms.
Build Directed And Undirected Edges
A directed edge is stored once, from source to target. An undirected edge is represented twice so traversal can move both ways. setdefault keeps the helper usable when a node has not appeared yet.
def add_directed_edge(graph, source, target):
graph.setdefault(source, set()).add(target)
def add_undirected_edge(graph, left, right):
graph.setdefault(left, set()).add(right)
graph.setdefault(right, set()).add(left)
graph = {}
add_undirected_edge(graph, "A", "B")
add_directed_edge(graph, "A", "C")
print(graph)
Store Weighted Neighbors
When an edge has a cost, label, or capacity, a neighbor value can be another dictionary. Keep the representation consistent so algorithms do not have to guess whether a neighbor is a node or an edge record.
graph = {
"A": {"B": 4, "C": 2},
"B": {"D": 3},
"C": {"D": 1},
"D": {},
}
for neighbor, weight in graph["A"].items():
print(neighbor, weight)
Traverse With Breadth First Search
BFS uses a queue and records a node when it is enqueued. Marking it visited at that point prevents duplicate work and gives shortest edge-count distances in an unweighted graph.
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = {start}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, set()):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
print(bfs({"A": {"B", "C"}, "B": {"D"}, "C": set(), "D": set()}, "A"))
Traverse With Depth First Search
DFS can use an explicit stack to avoid recursion-depth surprises. The visited set is still essential when cycles are possible, because a graph is not necessarily a tree.
def dfs(graph, start):
stack = [start]
visited = set()
order = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
stack.extend(reversed(tuple(graph.get(node, set()))))
return order
print(dfs({"A": {"B", "C"}, "B": {"A"}, "C": set()}, "A"))
Python’s official dictionary documentation explains the mapping structure commonly used for adjacency lists. Related references include breadth-first search, list intersection, and sets for unique neighbors.
For related graph traversal and neighbor storage, compare BFS, list intersection, and sets when choosing an adjacency-list representation.
Frequently Asked Questions
What is an adjacency list in Python?
It is usually a dictionary mapping each graph node to a collection of neighboring nodes or edge records.
How do I represent an undirected edge?
Add each endpoint to the other endpoint’s neighbor collection so traversal can move in both directions.
Should adjacency-list neighbors be lists or sets?
Use lists when edge order or duplicate edges matter, and sets when neighbor uniqueness and fast membership checks matter.
How do BFS and DFS use an adjacency list?
They repeatedly look up the current node’s neighbors, using a queue for breadth-first traversal or a stack/recursion for depth-first traversal.