How to represent a graph in Python

Graph representation in Python is a core skill for applications from social networks to route mapping. Python’s data structures offer flexible ways to model these complex relationships between objects.

In this article, you'll explore key representation techniques, complete with practical tips, real-world applications, and debugging advice to help you select and implement the best method for your project.

Using dictionaries for adjacency lists

graph = {
   'A': ['B', 'C'],
   'B': ['A', 'D', 'E'],
   'C': ['A', 'F'],
   'D': ['B'],
   'E': ['B', 'F'],
   'F': ['C', 'E']
}
print(f"Neighbors of B: {graph['B']}")--OUTPUT--Neighbors of B: ['A', 'D', 'E']

An adjacency list is a popular way to represent a graph, and Python's dictionaries are a natural fit. In the graph dictionary, each key is a node, and its value is a list of all directly connected neighbors. This structure makes looking up a node's connections, such as graph['B'], an efficient operation.

This method is favored for a few key reasons:

• Speed: Finding a node's neighbors is fast because it's a simple dictionary lookup.
• Flexibility: Adding or removing nodes and edges is straightforward since you're just manipulating dictionary entries and lists.

Basic graph representations

While adjacency lists are a common starting point, Python’s flexibility allows for other foundational representations like adjacency matrices, edge lists, and object-oriented structures.

Using nested lists for adjacency matrix

# Nodes are 0=A, 1=B, 2=C, 3=D
matrix = [
   [0, 1, 1, 0],  # A's connections
   [1, 0, 0, 1],  # B's connections
   [1, 0, 0, 1],  # C's connections
   [0, 1, 1, 0]   # D's connections
]
print(f"Is B connected to D? {bool(matrix[1][3])}")--OUTPUT--Is B connected to D? True

An adjacency matrix uses a nested list to form a grid where both rows and columns represent nodes. A 1 at a specific position, like matrix[1][3], signifies a direct connection between node 1 (B) and node 3 (D), while a 0 means there isn't one. This structure has distinct trade-offs.

• Fast lookups: You can check for an edge between any two nodes almost instantly.
• Memory usage: It can be inefficient for sparse graphs—graphs with few connections—since it stores a value for every possible pair of nodes.

Using edge list representation

edges = [('A', 'B'), ('A', 'C'), ('B', 'D'),
        ('C', 'D'), ('B', 'A'), ('C', 'A'),
        ('D', 'B'), ('D', 'C')]
node = 'A'
neighbors = [v for u, v in edges if u == node]
print(f"Neighbors of {node}: {neighbors}")--OUTPUT--Neighbors of A: ['B', 'C']

An edge list is one of the most straightforward ways to represent a graph. It’s simply a list of tuples, where each tuple like ('A', 'B') represents a direct connection from one node to another. This format is intuitive and easy to build, especially when you're reading data from a file.

• Simplicity: It directly models the connections in your graph without complex nesting.
• Performance: Finding a node's neighbors requires iterating through the entire edges list, which can be slow for large graphs compared to other methods.

Using classes for object-oriented representation

class Graph:
   def __init__(self):
       self.nodes = {}
       
   def add_edge(self, u, v):
       if u not in self.nodes: self.nodes[u] = []
       if v not in self.nodes: self.nodes[v] = []
       self.nodes[u].append(v)

g = Graph()
for edge in [('A', 'B'), ('A', 'C'), ('B', 'D')]:
   g.add_edge(*edge)
print(g.nodes)--OUTPUT--{'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}

An object-oriented approach encapsulates your graph's logic within a dedicated Graph class. Internally, it uses a dictionary to manage an adjacency list, but it bundles the data (nodes) and the operations that modify it (like add_edge) into a single, organized structure.

• Encapsulation: This keeps all graph-related behavior together, making your code cleaner and easier to manage as your project grows.
• Extensibility: You can easily add more functionality by defining new methods on the Graph class, such as for removing nodes or finding paths.

Advanced graph libraries and techniques

Building on these foundational techniques, you can leverage Python’s powerful libraries and modern features like dataclasses to create more efficient and robust graph structures.

Using the NetworkX library

import networkx as nx

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D')])
print(f"Graph info: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges")
print(f"Neighbors of A: {list(G.neighbors('A'))}")--OUTPUT--Graph info: 4 nodes, 3 edges
Neighbors of A: ['B', 'C']

For more complex tasks, the NetworkX library is a powerful choice that handles the low-level details for you. It provides a robust Graph object with a rich set of built-in methods. In the example, edges are added efficiently using add_edges_from, and inspecting the graph is simple with methods like number_of_nodes() and neighbors().

• Optimized performance: It’s built for speed and can handle large, complex graphs effectively.
• Rich functionality: The library comes packed with algorithms for pathfinding, centrality analysis, and more, saving you significant development time.

Using NumPy for efficient adjacency matrices

import numpy as np

# Create a 4x4 adjacency matrix for a graph
adj_matrix = np.array([
   [0, 1, 1, 0],
   [1, 0, 0, 1],
   [1, 0, 0, 1],
   [0, 1, 1, 0]
])
degree = np.sum(adj_matrix, axis=1)
print(f"Node degrees: {degree}")--OUTPUT--Node degrees: [2 2 2 2]

Using NumPy for an adjacency matrix is a smart move for performance-critical applications. While functionally similar to a nested list, a NumPy array is more memory-efficient and unlocks powerful, high-speed computations.

• Vectorized Operations: Instead of slow Python loops, you can use optimized functions. For example, np.sum with axis=1 quickly calculates the degree of every node by summing each row—all in one go.
• Memory Savings: NumPy arrays are more compact than Python lists, which is especially beneficial for large, dense graphs.

Using dataclasses for modern graph implementation

from dataclasses import dataclass, field
from typing import Dict, List, Set

@dataclass
class Graph:
   edges: Dict[str, Set[str]] = field(default_factory=dict)
   
   def add_edge(self, u: str, v: str) -> None:
       if u not in self.edges: self.edges[u] = set()
       if v not in self.edges: self.edges[v] = set()
       self.edges[u].add(v)

g = Graph()
g.add_edge('A', 'B')
print(g.edges)--OUTPUT--{'A': {'B'}, 'B': set()}

Python's dataclasses offer a modern, clean way to define classes that primarily store data. The @dataclass decorator automatically generates special methods like __init__, which means you write less boilerplate code. It’s a great way to get the benefits of an object-oriented design with more conciseness.

• The field(default_factory=dict) is used to safely initialize the mutable edges attribute, ensuring each new graph gets its own dictionary.
• Using a set for neighbors is also a key improvement. It automatically prevents duplicate edges and makes checking for connections very efficient.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. Describe what you want to build, and Replit Agent can create it—complete with databases, APIs, and deployment.

The graph representation techniques you've explored, from simple adjacency lists to using libraries like NetworkX, are the building blocks for powerful tools. Replit Agent can turn these concepts into production-ready applications.

• Social connection visualizer: Build a tool that maps relationships in a social network and calculates key metrics like a user's number of connections.
• Logistics route planner: Create an application that models warehouse locations as nodes and routes as edges to find the most efficient delivery paths.
• Project dependency tracker: Deploy a utility that parses a codebase to visualize how different modules and functions are interconnected.

Describe your idea for a graph-based application, and Replit Agent can write the code, test it, and deploy it automatically, all from your browser.

Common errors and challenges

When working with graphs in Python, a few common challenges can trip you up, even with a solid representation method.

• Error when accessing non-existent nodes: A frequent issue with dictionary-based graphs is the KeyError that occurs when you try to access a node that doesn't exist. To avoid crashing your program, use the get() method to safely retrieve nodes or check for a node's presence before accessing it.
• Forgetting to add bidirectional edges: In an undirected graph, an edge from node A to B must be mirrored with an edge from B back to A. Forgetting the return path creates an inconsistent graph where traversals can fail or produce incorrect results.
• Missing disconnected components: A standard traversal like dfs() only explores nodes reachable from its starting point. If your graph has separate, unconnected "islands" of nodes, you must iterate through all nodes and start a new traversal for each unvisited one to cover the entire graph.

Error when accessing non-existent nodes in dictionary graphs

A common tripwire when using dictionaries for graphs is the KeyError. It occurs when you try to access a node that hasn't been defined, like asking for graph['D'] when 'D' isn't a key. The following code demonstrates this exact scenario.

graph = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
neighbors = graph['D']  # This will raise KeyError
print(f"Neighbors of D: {neighbors}")

The program crashes because it tries to fetch graph['D'] directly, but the 'D' key doesn't exist in the dictionary, raising a KeyError. The following code demonstrates a safer way to access nodes and avoid this error.

graph = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
neighbors = graph.get('D', [])
print(f"Neighbors of D: {neighbors}")

The fix is to use the dictionary's get() method. Instead of crashing, graph.get('D', []) safely returns a default value—an empty list []—when the key 'D' isn't found. This approach is crucial when you're not sure if a node exists, like when processing external data or user input. It prevents KeyError exceptions and keeps your program from stopping unexpectedly.

Forgetting to add bidirectional edges in undirected graphs

In undirected graphs, every connection is a two-way street. If node A connects to B, B must also connect back to A. Forgetting this reciprocal link creates a one-way path, leading to an inconsistent graph where traversals can fail. The following code demonstrates this common oversight.

graph = {}
edges = [('A', 'B'), ('B', 'C'), ('A', 'C')]
for u, v in edges:
   if u not in graph: graph[u] = []
   graph[u].append(v)
print(graph)  # C has no outgoing edges

The loop processes each (u, v) tuple by only adding v to u's adjacency list. This creates one-way paths, leaving nodes like C without outgoing edges. The following code demonstrates the correct approach.

graph = {}
edges = [('A', 'B'), ('B', 'C'), ('A', 'C')]
for u, v in edges:
   if u not in graph: graph[u] = []
   if v not in graph: graph[v] = []
   graph[u].append(v)
   graph[v].append(u)  # Add reverse edge
print(graph)

The solution is to manually create the two-way connection. For each pair like ('A', 'B') from your edge list, you add the forward connection and then explicitly add the reverse with graph[v].append(u). This ensures the graph is truly undirected. It's a crucial step whenever you're building a graph from a simple list of pairs where connections are meant to be reciprocal, like in a social network.

Missing disconnected components with dfs()

A standard dfs() traversal only explores nodes reachable from its starting point. If your graph has separate, unconnected components, the function will miss them entirely. The following code demonstrates how a dfs() call only finds one part of the graph.

def dfs(graph, start):
   visited = set()
   def _dfs(node):
       visited.add(node)
       for neighbor in graph.get(node, []):
           if neighbor not in visited:
               _dfs(neighbor)
   _dfs(start)
   return visited

graph = {'A': ['B'], 'B': ['A'], 'C': ['D'], 'D': ['C']}
print(dfs(graph, 'A'))  # Only returns {'A', 'B'}

The dfs() function starts at 'A' and only visits its connected neighbor, 'B'. Since the 'C'-'D' component is unreachable from that starting point, the traversal is incomplete. The following code demonstrates the proper way to handle this.

def dfs_all(graph):
   visited = set()
   def _dfs(node):
       visited.add(node)
       for neighbor in graph.get(node, []):
           if neighbor not in visited:
               _dfs(neighbor)
   
   for node in graph:
       if node not in visited:
           _dfs(node)
   return visited

graph = {'A': ['B'], 'B': ['A'], 'C': ['D'], 'D': ['C']}
print(dfs_all(graph))  # Returns all nodes

The solution in dfs_all() is to loop through every node in the graph. It only starts a new traversal with its internal _dfs() function if a node hasn't already been visited. This simple check ensures that even if your graph has separate, unconnected "islands" of nodes, your traversal will eventually find and explore all of them. You'll need this approach whenever your data might not form a single, fully connected structure.

Real-world applications

Moving beyond implementation details and errors, these graph structures power applications from social network analysis to product recommendation engines.

Finding common connections in social networks

Adjacency lists are ideal for modeling social networks, allowing you to find mutual friends by simply calculating the intersection of two users' connection sets.

# Social network as an adjacency list
network = {
   'Alice': ['Bob', 'Charlie', 'David'],
   'Bob': ['Alice', 'Emma'],
   'Charlie': ['Alice', 'Frank'],
   'David': ['Alice', 'Emma'],
   'Emma': ['Bob', 'David', 'Frank'],
   'Frank': ['Charlie', 'Emma']
}

def common_connections(graph, person1, person2):
   return set(graph[person1]) & set(graph[person2])

common = common_connections(network, 'Bob', 'David')
print(f"Common connections between Bob and David: {common}")

The network dictionary models a social graph where each person maps to their list of friends. The core logic is in the common_connections function, which efficiently finds mutual friends between two people.

• It converts each person's friend list into a Python set. Sets are collections that are highly optimized for this kind of task.
• It then uses the intersection operator (&) to find the names that appear in both sets, giving you the mutual connections.

Using graph traversal for product recommendations

By treating purchase history as a graph, you can traverse from a specific product to its buyers and then to other items they've purchased, forming the basis of a simple recommendation engine.

# User purchase history (user -> products graph)
purchases = {
   'user1': ['productA', 'productB', 'productC'],
   'user2': ['productA', 'productD'],
   'user3': ['productB', 'productC', 'productE'],
   'user4': ['productA', 'productB']
}

# Find which users purchased productA
productA_users = [user for user, products in purchases.items()
                 if 'productA' in products]

# Find other products these users purchased
recommendations = set()
for user in productA_users:
   for product in purchases[user]:
       if product != 'productA':
           recommendations.add(product)

print(f"Recommendations for users who bought productA: {recommendations}")

This code generates product suggestions based on shared purchase behavior. It operates in two main steps:

• First, a list comprehension creates productA_users by filtering the purchases dictionary for everyone who bought 'productA'.
• Then, it iterates through only those users, collecting all other products they bought into a recommendations set. Using a set ensures the final list of suggestions contains no duplicates.

Get started with Replit

Put your knowledge into practice by building a real tool. Just tell Replit Agent what you want: “build a tool to find mutual friends” or “create a dependency visualizer for a Python project.”

It will write the code, test for errors, and deploy your application automatically. Start building with Replit and bring your graph-based tool to life.