What Is a Graph?

Dots and lines

A graph is a set of vertices (dots) joined by edges (lines). Trees and linked lists are special graphs.

Think of it like this: Cities and roads, people and friendships, web pages and links.

The adjacency list

For vertices numbered 0 … n − 1, keep a vector of neighbours for each: vector<vector<int>>.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 4;
    vector<pair<int, int>> roads = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
    vector<vector<int>> g(n);
    for (auto [a, b] : roads) {
        g[a].push_back(b);
        g[b].push_back(a);          // two-way
    }
    for (int v = 0; v < n; v++) {
        cout << v << ":";
        for (int w : g[v]) cout << ' ' << w;
        cout << endl;
    }
    return 0;
}

Output

0: 1 2
1: 0 3
2: 0 3
3: 1 2

Tip: An adjacency matrix (m[a][b] = 1 for an edge) checks one edge in O(1) but needs n² memory – too much for big, sparse graphs.