Graphs

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.

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

Basic Implementation

basic.cpp
Replay: real traced execution (multi-file project)
#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;
}

  1. dist ← {1: 0}

    18std::map<int, int> parent;19dist[src] = 0;20parent[src] = 0;
    values this step{1: 0}dist

  2. parent ← {1: null}

    19dist[src] = 0;20parent[src] = 0;21std::queue<int> q;
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    23while (!q.empty()) {24    int v = q.front();25    q.pop();
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    39}40std::cout << "[";41for (size_t i = 0; i < path.size(); ++i) {
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1, 2, 4, 5, 6]

    44}45std::cout << "]" << std::endl;46std::cout << dist[dst] << std::endl;
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    45std::cout << "]" << std::endl;46std::cout << dist[dst] << std::endl;47return 0;
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    45std::cout << "]" << std::endl;46std::cout << dist[dst] << std::endl;47return 0;
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

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.