Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

basic.cpp

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

int main() {
    std::map<int, std::vector<int>> adj;
    adj[1] = {2, 3};
    adj[2] = {1, 4};
    adj[3] = {1, 4};
    adj[4] = {2, 3, 5};
    adj[5] = {4, 6};
    adj[6] = {5};

    int src = 1;
    int dst = 6;
    std::map<int, int> dist;
    std::map<int, int> parent;
    dist[src] = 0;
    parent[src] = 0;
    std::queue<int> q;
    q.push(src);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int nb : adj[v]) {
            if (dist.find(nb) == dist.end()) {
                dist[nb] = dist[v] + 1;
                parent[nb] = v;
                q.push(nb);
            }
        }
    }
    std::vector<int> path;
    int node = dst;
    while (node != 0) {
        path.push_back(node);
        node = parent[node];
    }
    std::cout << "[";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << path[path.size() - 1 - i];
    }
    std::cout << "]" << std::endl;
    std::cout << dist[dst] << std::endl;
    return 0;
}

Complexity

Time: O((V + E) log V) in this C++ source because std::map lookups and insertions are ordered-tree operations
Space: O(V)

Implementation notes

In C++, the adjacency list is a std::map<int, std::vector<int>>, so each vertex maps to a vector of neighbour int values in the order written in basic.cpp.
std::map<int, int> dist is both the distance table and the visited check via dist.find(nb) == dist.end(). parent stores predecessor ids, with 0 as the source sentinel used by the reconstruction loop. These map operations are ordered lookups, not average O(1) hash-table probes.
std::queue<int> stores copied vertex ids; the code uses front(), pop(), and push(nb) while mutating dist and parent only when a neighbour is first discovered.
The replayed queue states are [2, 3], [3, 4], [4], [5], [6], and [], with dist[6] ending at 4 and parent[6] set to 5.
Path reconstruction pushes 6, 5, 4, 2, 1 into a std::vector<int> path and prints it in reverse index order as [1, 2, 4, 5, 6], followed by dist[dst] on the next line.
Visible allocation is the map nodes, adjacency/path vectors, and queue storage; visible mutation is distance/parent insertion, queue updates, and path.push_back. The trace's weighted contrast shows the limit: this BFS path minimizes edge count, not total edge weight.

layers equal distance BFS order equals distance in an unweighted graph.