Why bother with adjacency lists instead of just using a 2D array?

When you first look at graphs, a 2D array (an adjacency matrix) seems like the obvious choice. If city A connects to city B, you just set matrix[A][B] = 1. Simple, right? But here is the problem: most real-world graphs are "sparse."

Think about a flight network. There might be 500 airports in the world, but any single airport only flies to a handful of others. In a matrix, you'd be allocating a 500x500 grid—250,000 cells—just to store maybe 2,000 actual flights. You're wasting a massive amount of memory on zeros. With an adjacency list, you only store the connections that actually exist. It turns your space complexity from $O(V^2)$ to $O(V + E)$, where $V$ is vertices and $E$ is edges. Unless your graph is incredibly dense, the list is almost always the way to go.

What's the cleanest way to actually structure this in C++?

You'll see some old textbooks use linked lists, but in modern C++, I almost always use a std::vector of std::vectors. Why? Cache locality. Jumping around memory with std::list is a performance killer. If your nodes are represented by integers (0, 1, 2...), a vector of vectors is incredibly efficient.

#include <iostream>
#include <vector>

class FlightGraph {
    int numAirports;
    // Each index in the outer vector represents an airport
    // The inner vector contains the IDs of airports it connects to
    std::vector<std::vector<int>> adjLists;

public:
    FlightGraph(int airports) : numAirports(airports) {
        adjLists.resize(airports);
    }

    void addFlight(int source, int destination) {
        // For an undirected graph (round trip), add both ways
        adjLists[source].push_back(destination);
        adjLists[destination].push_back(source);
    }

    void printNetwork() {
        for (int i = 0; i < numAirports; ++i) {
            std::cout < "Airport " < i < " connects to: ";
            for (int neighbor : adjLists[i]) {
                std::cout < neighbor < " ";
            }
            std::cout < "\n";
        }
    }
};

Notice I used resize() in the constructor. This ensures we don't have to call push_back on the outer vector, which prevents unnecessary reallocations as we build the graph.

How do I handle weights, like the distance between airports?

The simple vector<int> works for basic connectivity, but usually, you need more data—like the ticket price or the mileage between cities. In this case, you stop storing raw integers and start storing a small struct.

I've found that creating a dedicated Edge struct makes the code much more readable than using a std::pair, which leaves you wondering what first and second actually represent.

struct Edge {
    int destination;
    int distance;
};

// Now the graph looks like this:
std::vector<std::vector<Edge>> weightedAdjLists;

void addWeightedFlight(int source, int destination, int dist) {
    weightedAdjLists[source].push_back({destination, dist});
    weightedAdjLists[destination].push_back({source, dist});
}
By doing this, you've kept the memory efficiency of the adjacency list while adding the ability to run algorithms like Dijkstra's for finding the shortest path. It's a small change in structure that unlocks a lot of power.

📋 Practical Task

Build a Regional Airport Hub Mapper

Create a program that implements a graph using adjacency lists to model a regional flight network. Your program should:

• Initialize a graph with 6 airports (represented by IDs 0-5).
• Implement a method addEdge(int u, int v, int weight) that adds a bidirectional flight between two airports with a specific distance.
• Implement a method getConnections(int airportID) that prints all airports reachable from the given ID and the distance to each.
• Populate the graph with the following data:
  • 0 to 1 (500 miles)
  • 0 to 2 (300 miles)
  • 1 to 2 (100 miles)
  • 2 to 3 (800 miles)
  • 3 to 4 (200 miles)
  • 4 to 5 (150 miles)
  • 5 to 2 (600 miles)
• Call getConnections(2) and verify that it lists airports 0, 1, 3, and 5 with their correct distances.