Representing Relationships as Adjacency Lists

Welcome to Module 8! In our previous lessons, we explored various data structures like arrays, linked lists, trees, and heaps, each suited for different kinds of problems. We concluded by mastering the bounded heap, an elegant pattern for "Top K" problems. Now, we shift our focus to one of the most versatile and powerful data structures in computer science: the graph.

Graphs are used to model networks of all kinds—social networks, computer networks, road maps, dependencies between tasks, and much more. This module will equip you with the fundamental tools to work with them. Today's lesson is the essential first step: learning how to take raw relationship data and represent it in a way our algorithms can understand. By the end of this hour, you will be able to convert relationship data into the most common and efficient graph representation: the adjacency list.

What is a Graph?

At its core, a graph is a way to represent connections between objects. These objects are called vertices (or nodes), and the connections are called edges. Before we dive into code, let's build a quick, solid intuition for these concepts.

The following short video provides an excellent, fast-paced introduction to the world of graphs, defining the key terminology we'll be using throughout this module.

To summarize the key terms:

• Vertices (or Nodes): The individual items or entities in our dataset. For example, users in a social network, airports on a map, or tasks in a project plan.
• Edges: The links or relationships that connect pairs of vertices.
• Undirected Graph: Edges are two-way. If A is connected to B, B is also connected to A (e.g., a Facebook friendship).
• Directed Graph: Edges are one-way. A connection from A to B doesn't imply a connection from B to A (e.g., following someone on Twitter/X).
• Weighted Graph: Edges have a "cost" or "weight" associated with them, like the distance between two cities or the time it takes to complete a task.

How to Represent a Graph in Code

Now that we have the concepts, how do we translate them into a data structure? There are two primary methods: the adjacency matrix and the adjacency list. Choosing the right representation is crucial as it significantly impacts the performance of your graph algorithms.

The same Fireship video gives a quick overview of both.

While the video gives a great summary, understanding the trade-offs in space and time complexity is critical. For that, we'll turn to a more detailed textual resource.

The key takeaway is that for most problems you'll encounter, where the number of connections is much smaller than the total possible connections, the adjacency list is the superior choice for its space efficiency. For the rest of this course, it will be our default representation.

Building an Adjacency List

An adjacency list maps each vertex to a list (or set) of its direct neighbors. In JavaScript/TypeScript, a Map is a perfect tool for this, where keys are vertices and values are arrays or sets of adjacent vertices.

Here is a visual example of an undirected graph and its corresponding adjacency list.

And here is a directed graph.

The main task of this lesson is to perform the conversion from a simple list of edges, which is often how relationship data is given, into this powerful adjacency list structure.

For example, given this input (an edge list):
const edges = [['A', 'B'], ['B', 'C'], ['A', 'C']];

We want to produce this output (an adjacency list):

Map {
  'A' => ['B', 'C'],
  'B' => ['A', 'C'],
  'C' => ['B', 'A']
}

The algorithm is straightforward:

1. Initialize an empty Map.
2. Iterate through each edge [u, v] in the input list.
3. For each vertex in the edge (u and v), if it's not already a key in the map, add it with an empty list as its value.
4. Add v to the list of neighbors for u.
5. For an undirected graph, also add u to the list of neighbors for v.

The following resource walks through this exact process with a clear explanation and code.

A Practical Implementation in TypeScript

While a standalone function is useful, it's often better to encapsulate the graph logic within a class. This aligns with how you'd build larger, more maintainable systems.

Let's look at a class-based approach. The following video demonstrates creating a Graph class with addVertex and addEdge methods. A key insight it offers is using a Set instead of an Array for the neighbor list to prevent duplicate edges and provide efficient O(1) average time lookups.

Synthesizing these ideas, here is a simple and reusable Graph class in TypeScript that can be constructed directly from an edge list.

class Graph<T> {
    // We use a Map to store the adjacency list.
    // The key is the vertex, and the value is a Set of its neighbors.
    public adjacencyList: Map<T, Set<T>> = new Map();

    /**
     * Initializes the graph from a list of edges.
     * @param edges - An array of pairs, where each pair represents an edge.
     * @param directed - A boolean indicating if the graph is directed.
     */
    constructor(edges: T[][], directed: boolean = false) {
        // First, add all unique vertices from the edge list to the map.
        // This prevents errors if an edge connects to a vertex not seen before.
        for (const edge of edges) {
            for (const vertex of edge) {
                if (!this.adjacencyList.has(vertex)) {
                    this.adjacencyList.set(vertex, new Set());
                }
            }
        }

        // Now, add the edges.
        for (const edge of edges) {
            const [u, v] = edge;
            // Add v to the neighbor set of u.
            this.adjacencyList.get(u)!.add(v);

            // If the graph is undirected, add the reverse edge.
            if (!directed) {
                this.adjacencyList.get(v)!.add(u);
            }
        }
    }

    public printGraph(): void {
        for (const [vertex, neighbors] of this.adjacencyList.entries()) {
            const neighborsStr = [...neighbors].join(', ');
            console.log(`${vertex} -> ${neighborsStr}`);
        }
    }
}

// Example usage for an undirected graph:
const routes = [
    ['PHX', 'JFK'],
    ['LAX', 'JFK'],
    ['JFK', 'ORD'],
    ['PHX', 'LAX']
];

const flightGraph = new Graph(routes);
flightGraph.printGraph();

/*
Expected Output:
PHX -> JFK, LAX
JFK -> PHX, LAX, ORD
LAX -> JFK, PHX
ORD -> JFK
*/

This class provides a solid foundation. We can now easily create graph instances from raw data, which is the first step in solving any graph-based problem.

Conclusion

In this lesson, we made the conceptual leap into the world of graphs. We established what graphs are and, most importantly, learned how to represent them in code. This is a foundational skill for tackling a huge category of algorithmic problems.

Key Takeaways:

• A graph is a data structure for modeling entities (vertices) and their relationships (edges).
• The adjacency list is the most common and space-efficient way to represent sparse graphs, which are prevalent in real-world applications. Its space complexity is $O(|V|+|E|)$.
• An adjacency list can be implemented elegantly in TypeScript/JavaScript using a Map where keys are vertices and values are Arrays or Sets of their neighbors.
• We can systematically convert an edge list into an adjacency list by iterating through the edges and populating our map structure.

We now have the ability to build a graph. In our next lesson, we will learn how to explore it. We will implement Breadth-First Search (BFS), a fundamental traversal algorithm that allows us to systematically visit every vertex and edge, forming the basis for solving problems like finding the shortest path in an unweighted graph.