Step 1 of 6

Adjacency lists

Trees have strict rules: one root, one parent per node, no loops. A graph drops those rules. It's just a set of vertices (the things) connected by edges (the relationships), in any pattern. Road maps, social networks, the links between web pages, build dependencies and computer networks are all graphs.

Two choices describe a graph:

• Directed or undirected: a one-way street or a follow on social media is directed (a → b doesn't imply b → a); a friendship or a two-way road is undirected.
• Weighted or unweighted: whether edges carry a cost, like a distance.

Here, vertices are numbered 0..n-1. The standard representation is an adjacency list: for each vertex, the list of its neighbors.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> city = {"Oslo", "Bergen", "Trondheim", "Tromso"};
    std::vector<std::pair<int, int>> roads = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};

    std::vector<std::vector<int>> adj(city.size());
    for (auto [a, b] : roads) {
        adj[a].push_back(b);      // edge a -> b
        adj[b].push_back(a);      // roads are two-way: b -> a too
    }

    for (std::size_t v = 0; v < adj.size(); v++) {
        std::cout << city[v] << " (" << adj[v].size() << "):";
        for (int w : adj[v]) std::cout << " " << city[w];
        std::cout << "\n";
    }
}

Oslo (2): Bergen Trondheim
Bergen (2): Oslo Trondheim
Trondheim (3): Oslo Bergen Tromso
Tromso (1): Trondheim

How it works

• adj[v] is the list of v's neighbors. Its size is v's degree: how many edges touch it.
• For an undirected graph, each edge is stored twice, once from each end. For a directed graph, only adj[a].push_back(b).
• Looping over a vertex's neighbors is just a range-for over adj[v], which is exactly what every graph algorithm does.

Why not a matrix?

An alternative is an n × n table where m[a][b] says whether the edge exists. That uses n² memory no matter how few edges there are. Real graphs are usually sparse: a million users each with a few hundred friends. The adjacency list uses O(V + E) memory, proportional to what actually exists.

Your turn: write build(n, edges, directed) returning the adjacency list, and int max_degree(const std::vector<std::vector<int>>& adj) returning the largest number of neighbors any vertex has.

Next: Shortest path with BFS