Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a Graph Using an Adjacency List in Python

Graphs provide a useful way to model relationships between objects. A city map can represent intersections and roads, a social network can represent people and connections, and a web crawler can represent pages and hyperlinks. In Python, an adjacency list is one of the clearest and most practical structures for storing these relationships.

This approach keeps each vertex alongside the vertices it can reach. It usually uses less memory than an adjacency matrix, especially when most possible connections do not exist. That makes it a sensible choice for everything from a small Brisbane bus-route exercise to a large network-analysis task involving Australian cities.

Understanding The Graph Model

A graph consists of vertices, also called nodes, and edges connecting them. A vertex might represent a person, a location, or a software component. An edge records a relationship between two vertices. Graphs can be directed, where a connection has a single direction, or undirected, where movement works both ways.

For example, a road between Sydney and Canberra can be modelled as an undirected edge if travel is possible in either direction. A one-way link from a webpage to another page is directed. Graphs may also be weighted, meaning each edge stores a value such as distance, travel time, cost, or network latency.

An adjacency list stores a collection of neighbours for every vertex. A simple unweighted graph could be represented like this:

{
    "Sydney": ["Canberra", "Melbourne"],
    "Canberra": ["Sydney"],
    "Melbourne": ["Sydney"]
}

The dictionary keys are vertices, while each list contains their adjacent vertices. A set can replace a list when duplicate edges should be prevented and fast membership checks are important.

Building A Basic Adjacency List

A Python dictionary is enough for many graph problems. The add_vertex method ensures that a vertex exists even when it has no connections. The add_edge method then adds a relationship between two vertices.

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, source, destination):
        self.add_vertex(source)
        self.add_vertex(destination)
        self.adjacency_list[source].append(destination)

    def neighbours(self, vertex):
        return self.adjacency_list.get(vertex, [])

This implementation describes a directed graph. Calling add_edge("Sydney", "Canberra") means that Sydney points to Canberra, but Canberra does not automatically point back to Sydney. That behaviour suits one-way streets, task dependencies, and links between web pages.

A lookup for a missing vertex returns an empty list rather than raising a KeyError. This is convenient for traversal code, although some applications may prefer to raise an exception so that invalid input is detected immediately.

Supporting Undirected And Weighted Edges

For an undirected graph, insert each endpoint into the other endpoint’s neighbour list. This creates two directed entries that together represent one two-way relationship.

class UndirectedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        self.adjacency_list.setdefault(vertex, [])

    def add_edge(self, first, second):
        self.add_vertex(first)
        self.add_vertex(second)

        self.adjacency_list[first].append(second)
        self.adjacency_list[second].append(first)

If the same edge can be added repeatedly, duplicate values may appear. One option is to check before appending, although that adds a linear search through the neighbour list. Another option is to store neighbours in sets:

from collections import defaultdict

graph = defaultdict(set)
graph["Sydney"].add("Canberra")
graph["Canberra"].add("Sydney")

Weighted edges need a little extra structure. A neighbour can be stored as a tuple containing the destination and weight:

weighted_graph = {
    "Sydney": [("Canberra", 286)],
    "Canberra": [("Sydney", 286)]
}

The number 286 could represent kilometres, minutes, or another application-specific measurement. For more complex systems, a small Edge dataclass can make the meaning of each field clearer.

Traversing Neighbours With BFS And DFS

Once the adjacency list exists, graph traversal algorithms can explore it. Breadth-first search visits nearby vertices first and uses a queue. It is useful for finding the shortest path in an unweighted graph, such as the fewest connections between two accounts.

from collections import deque

def breadth_first_search(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        current = queue.popleft()
        order.append(current)

        for neighbour in graph.get(current, []):
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

    return order

The visited set is essential. Without it, an undirected graph containing Sydney and Canberra would keep moving between those two vertices. In a network of tram stops around Melbourne, it also prevents the same stop from being processed repeatedly through different routes.

Depth-first search follows one path as far as possible before backtracking. It can be implemented recursively or with an explicit stack. The explicit version avoids Python’s recursion-depth limit for very deep graphs.

def depth_first_search(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        current = stack.pop()

        if current in visited:
            continue

        visited.add(current)
        order.append(current)

        for neighbour in reversed(graph.get(current, [])):
            if neighbour not in visited:
                stack.append(neighbour)

    return order

For weighted graphs, BFS is generally not enough to find the cheapest route. Algorithms such as Dijkstra’s algorithm, Bellman–Ford, and Johnson’s algorithm use edge weights in different ways. A useful companion explanation is this Johnson algorithm tutorial, particularly when shortest paths are required between many pairs of vertices.

Practical Checks For Reliable Graph Code

Graph code can appear correct on a small example while failing on disconnected vertices, repeated edges, or an empty input. Testing a few distinct shapes makes the implementation more dependable before it is used in a larger project.

Useful cases to test include:

Input validation also matters. Decide whether self-loops such as A -> A are allowed, whether duplicate edges should be ignored, and whether a missing start vertex should return an empty traversal or raise an error. A clear policy prevents surprising results later.

When inspecting a graph during development, print each vertex and its neighbours in a stable order. Sorting is helpful for readable tests, although it may be unnecessary overhead in production code. For a local coding meetup in Perth or an assignment run on a university lab machine, deterministic output makes debugging much easier.

A robust implementation should also consider:

Time And Space Complexity

Let V represent the number of vertices and E represent the number of edges. An adjacency list stores the vertices and the connections that actually exist, so its space complexity is O(V + E). For an undirected graph, every edge is usually stored twice, but the complexity remains the same.

Adding a vertex with a dictionary takes average O(1) time. Adding an edge is also average O(1) when duplicate checking is not required. Looking up one vertex’s neighbours is average O(1), followed by the cost of processing the returned collection.

A complete BFS or DFS traversal runs in O(V + E) time because each reachable vertex and each relevant adjacency entry is examined a bounded number of times. This is more efficient than scanning a full V × V matrix when the graph is sparse.

An adjacency matrix can still be preferable when the graph is dense or when constant-time checks for a particular edge are central to the application. The right representation depends on the graph’s density, the most common operations, and memory limits rather than on a single universal rule.

Extending The Python Representation

A graph class can include methods for removing vertices and edges, checking whether a connection exists, and returning all vertices. For production code, type hints improve readability and help tools detect inconsistent data.

from collections import defaultdict

class TypedGraph:
    def __init__(self):
        self.adjacency_list: dict[str, set[str]] = defaultdict(set)

    def add_edge(self, source: str, destination: str) -> None:
        self.adjacency_list[source].add(destination)
        self.adjacency_list[destination].add(source)

    def has_edge(self, source: str, destination: str) -> bool:
        return destination in self.adjacency_list.get(source, set())

Sets provide natural duplicate protection, but they do not preserve insertion order as the main purpose of the structure. If traversal order matters for output or testing, a list may be more suitable, or the neighbours can be sorted before processing.

Graph structures also appear in machine learning workflows. A graph may describe relationships between observations, features, or hidden states, while probability models analyse uncertain assignments. For background on another algorithmic idea involving iterative parameter estimation, see this expectation maximisation guide.

For a larger application, separate the graph’s data model from algorithms that operate on it. The same adjacency list can then support BFS, DFS, shortest-path search, cycle detection, topological sorting, and connected-component analysis without duplicating the storage logic.

Choosing The Right Representation

An adjacency list is usually the best starting point when a graph has relatively few edges compared with the number of possible edges. Road networks, dependency graphs, and social connections often have this shape. The representation is compact and makes it natural to iterate through the actual neighbours of a vertex.

An adjacency matrix has different strengths. It uses a two-dimensional array and can answer “is there an edge from u to v?” in O(1) time. However, it requires O(V²) space, which becomes wasteful when most pairs are not connected. A matrix may suit a small, dense graph used for repeated edge-existence queries.

In practical Australian examples, an adjacency list can model regional flight routes, paths between stations on Sydney’s train network, or links between services hosted across data centres in Canberra. The same Python pattern applies whether the labels are place names, integers, URLs, or custom objects.

The central design decision is to choose storage that matches the algorithms and queries your program performs. Once each vertex has a reliable collection of neighbours, the graph becomes a flexible foundation for searching, routing, dependency analysis, and many other computer science problems.