Hello! Welcome to the first lesson in our module on Graph Traversal Algorithms.
In the last module, we wrapped up Dynamic Programming by tackling the Coin Change problems. We are now shifting gears to another incredibly important topic for technical interviews: graphs. Graphs are fundamental structures used to model networks and relationships, from social connections on platforms like LinkedIn to the dependencies in the software projects you build.
Today, we'll start with the absolute foundation. Before we can traverse a graph or find the shortest path, we need to know how to represent it in code. This lesson is dedicated to mastering the two primary ways to do this, which directly addresses our learning outcome: Represent graphs using adjacency lists and adjacency matrices.
By the end of this lesson, you'll understand the structure, space-time trade-offs, and implementation of both representations, enabling you to choose the right tool for any graph problem you encounter in an interview.
1. What is a Graph? Key Terminology
First, let's establish a shared vocabulary. A graph is a data structure composed of vertices (also called nodes) and edges that connect them. That's the simple definition, but there are a few key distinctions and terms that are crucial to know.
To get a quick but thorough overview of this core terminology, please watch the first few minutes of the following video.
Graphs: Edge List, Adjacency Matrix, Adjacency List, DFS, BFS - DSA Course in Python Lecture 11
This video from the Greg Hogg DSA course provides a clear and practical introduction to graph terminology. It will help you quickly grasp the essential concepts before we dive into representations.
Watch from the beginning until 03:49. Focus on understanding the definitions of: Vertices and Edges Directed vs. Undirected graphs Cyclic graphs (graphs with loops)
To summarize and expand on the video's points:
- An undirected graph has two-way edges (like a Facebook friendship).
- A directed graph has one-way edges (like a Twitter follow).
- The neighbors of a vertex
vare all the vertices directly connected tovby an edge. - The degree of a vertex in an undirected graph is its number of neighbors.
- A graph is sparse if it has relatively few edges compared to the maximum possible number of edges. Most real-world graphs (social networks, road maps) are sparse.
- A graph is dense if it has many edges, approaching the maximum possible.
With these terms in mind, let's explore how to store this structure in memory.
2. Graph Representations
There are two standard ways to represent a graph in code: the adjacency matrix and the adjacency list. Your choice between them involves a classic time-space tradeoff, which is a favorite topic for interviewers to probe.
The image below shows a simple undirected and directed graph, each represented using both an adjacency matrix and an adjacency list. Keep this visual in mind as we explore each one.
2.1. The Adjacency Matrix
An adjacency matrix is a 2D array (a list of lists in Python) of size , where is the number of vertices. We use it to mark the existence of edges:
matrix[i][j] = 1if there is an edge from vertexito vertexj.matrix[i][j] = 0otherwise.
For a weighted graph, instead of storing 1, you would store the edge's weight. For an undirected graph, the matrix will be symmetric (matrix[i][j] == matrix[j][i]) because an edge from i to j implies an edge from j to i.
The primary advantage of an adjacency matrix is that checking for an edge between two vertices is extremely fast—it's an lookup.
Complete Guide to Graph Data Structure: BFS, DFS ...
To see the pros and cons in more detail, please read the section on Adjacency Matrix Representation from this guide on singhajit.com.
Read the subsection titled 'Adjacency Matrix Representation'. Focus on its space complexity, pros, and cons.
The biggest drawback is its space complexity: . For a sparse graph with millions of nodes but only a few connections per node (like a social network), storing a massive matrix full of zeros is highly inefficient.
2.2. The Adjacency List
The adjacency list is the most common representation for graphs, especially in interview settings. It consists of a map or an array where each vertex maps to a list containing all of its neighbors.
In Python, this is typically implemented with a hash map (a dictionary) where keys are the vertices and values are lists of their adjacent vertices. Your experience with Python's dict and data manipulation makes this a very natural fit.
Complete Guide to Graph Data Structure: BFS, DFS ...
Now, let's get the same overview for the adjacency list. This is the representation you'll use most often.
Read the subsection titled 'Adjacency List in Data Structure'. Again, focus on its space complexity, pros, and cons.
The space complexity is , where is the number of vertices and is the number of edges. This is far more efficient for the sparse graphs common in real-world problems. The main tradeoff is that checking for a specific edge (u, v) now takes time, as you have to scan the list of u's neighbors.
3. Implementation in Python
Now, let's see how to build these representations from a common input format: a list of edges. For example, edges = [[0, 1], [1, 2], [2, 0]].
The following video demonstrates how to convert an edge list into both an adjacency matrix and an adjacency list in Python. The use of collections.defaultdict for the adjacency list is a very common and efficient pattern.
Graphs: Edge List, Adjacency Matrix, Adjacency List, DFS, BFS - DSA Course in Python Lecture 11
This part of Greg Hogg's video provides clean, practical Python code for building both representations from scratch. Pay close attention to the defaultdict implementation.
Watch the following two segments: 22:25 - 24:48: How to build an adjacency matrix from an edge list. Notice the simple logic for making it undirected. 24:48 - 26:38: How to build an adjacency list using defaultdict(list). This is a key pattern to remember for interviews.
4. Head-to-Head Comparison: The Interview Trade-offs
In an interview, stating that you'll use an adjacency list is good, but explaining why by comparing it to an adjacency matrix is great. You need to be ready to discuss the trade-offs.
Here is a summary table that captures the essential differences. This is a high-yield piece of information for your interview preparation.
| Operation | Adjacency List | Adjacency Matrix | When to Use |
|---|---|---|---|
| Check if edge (u, v) exists | or | Matrix: If you need frequent, fast edge lookups. | |
| Get all neighbors of u | List: If you need to iterate over neighbors often. | ||
| Space Complexity | List: For sparse graphs. Matrix: For dense graphs. |
This information is well-summarized in the comparison section of the singhajit.com guide.
Complete Guide to Graph Data Structure: BFS, DFS ...
For a final reinforcement of these trade-offs, read this short comparison section.
Read the section 'Adjacency List vs Adjacency Matrix: Comparison'. The table here is an excellent summary for quick review.
Test your understanding!
You are designing a system to model flight routes for a major airline network with thousands of airports. You need to perform two main types of queries:
- "What are all the direct flights out of Chicago O'Hare (ORD)?" (iterating neighbors)
- "Is there a direct flight from New York (JFK) to Tokyo (HND)?" (checking a specific edge)
The number of airports (vertices) is large, but any given airport has a relatively small number of direct routes compared to the total number of airports.
Which graph representation would you choose and why?
Show answer
The adjacency list is the better choice.
Reasoning:
- Sparsity: The graph is sparse. There are thousands of airports (), but each airport only has flights to a fraction of them. An adjacency matrix () would be enormous and mostly filled with zeros, wasting a huge amount of memory. An adjacency list () is much more space-efficient.
- Query Types: While the edge-check query is faster with a matrix, the "all direct flights" query is much more efficient with a list ( vs. ). Given that iterating over neighbors is a primary use case for graph algorithms (like finding connecting flights), optimizing for this operation is crucial. The slightly slower edge check is an acceptable trade-off for the massive space savings and efficient neighbor traversal.
Conclusion
Excellent work! You've now covered the essential first step in tackling any graph problem: representing the graph itself. Understanding these data structures is non-negotiable for graph-based interview questions.
Key Takeaways:
- Graphs are modeled by vertices and edges and can be directed or undirected.
- An Adjacency Matrix uses space but provides edge lookups. It's best for dense graphs or when frequent edge checks are the priority.
- An Adjacency List uses space and is efficient for iterating over neighbors (). It is the standard choice for the sparse graphs typically found in interview problems and real-world applications.
- In Python, an adjacency list is most effectively implemented using a
defaultdict(list).
Preview of the Next Lesson:
Now that we know how to store a graph, we're ready to explore it. In our next lesson, we will implement our first fundamental traversal algorithm: Breadth-First Search (BFS). You'll learn how to use a queue to explore a graph layer by layer, which is the key to finding the shortest path in unweighted graphs.