Build a Graph as an Adjacency List

Represent an undirected graph as a map from each vertex to its list of neighbours. For every edge (u, v), append v to adj[u] and u to adj[v]. Neighbour lists keep insertion order so the graph is a stable, deterministic fixture for the search lessons.

Algorithm

Basic Implementation

basic.cpp

#include <iostream>
#include <vector>
#include <map>

int main() {
    std::vector<std::pair<int, int>> edges = {
        {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}};
    std::map<int, std::vector<int>> adj;
    for (const auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }
    std::cout << "{";
    bool first = true;
    for (const auto& kv : adj) {
        if (!first) std::cout << ", ";
        std::cout << kv.first << ": [";
        for (size_t i = 0; i < kv.second.size(); ++i) {
            if (i > 0) std::cout << ", ";
            std::cout << kv.second[i];
        }
        std::cout << "]";
        first = false;
    }
    std::cout << "}" << std::endl;
    return 0;
}

The graph fixture is pinned once, then the adjacency list writes each undirected edge in both directions.

Step 1 - Pinned graph fixture

The six vertices and six undirected edges are the shared fixture for BFS and DFS.

Step 2 - Final adjacency list

Each row lists neighbours in the same insertion order used by the lesson.

Complexity

Build: O(V + E)
Space: O(V + E)

Implementation notes

C++: a std::map<int, std::vector<int>> keeps vertices in sorted order, and each vector stores neighbours appended in edge order.
The replay shows the adjacency list after each edge is added, matching the lesson spec.

adjacency list Each edge adds two directed entries, one in each direction.