Graphs in C++: BFS, DFS and Dijkstra

Graphs model networks of things: cities and roads, users and friendships, web pages and links, tasks and dependencies. With the STL, a graph is just a vector of vectors, and the three core algorithms – BFS, DFS and Dijkstra – are each about twenty lines. They appear in nearly every DSA round.

Adjacency list

#include <iostream>
#include <vector>

int main() {
    int n = 5;
    std::vector<std::vector<int>> adj(n);
    auto add_edge = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };   // undirected
    add_edge(0, 1); add_edge(0, 2); add_edge(1, 3); add_edge(2, 3); add_edge(3, 4);

    for (int u = 0; u < n; u++) {
        std::cout << u << ':';
        for (int v : adj[u]) std::cout << ' ' << v;
        std::cout << '\n';
    }
    return 0;
}

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

An adjacency list uses O(V + E) memory and lets you visit a node's neighbours directly. An adjacency matrix (vector<vector<bool>> g(n, vector<bool>(n))) answers "is there an edge u–v?" in O(1) but needs O(V²) memory – only practical for small, dense graphs.

BFS: fewest edges

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

int main() {
    int n = 6;
    std::vector<std::vector<int>> adj(n);
    for (auto [u, v] : std::vector<std::pair<int, int>>{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}}) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<int> dist(n, -1), parent(n, -1);
    std::queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {                 // not visited yet
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    for (int v = 0; v < n; v++) std::cout << "dist to " << v << " = " << dist[v] << '\n';

    std::vector<int> path;                       // rebuild the path 0 → 5 from parents
    for (int v = 5; v != -1; v = parent[v]) path.insert(path.begin(), v);
    std::cout << "path:";
    for (int v : path) std::cout << ' ' << v;
    std::cout << '\n';
    return 0;
}

dist to 0 = 0
dist to 1 = 1
dist to 2 = 1
dist to 3 = 2
dist to 4 = 3
dist to 5 = 4
path: 0 1 3 4 5

DFS: connected components and grids

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

std::vector<std::string> grid{
    "11000",
    "11010",
    "00011",
    "10000",
};
int rows = 4, cols = 5;

void sink(int r, int c) {                                  // flood fill from (r, c)
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';                                      // mark visited
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
}

int main() {
    int islands = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == '1') { islands++; sink(r, c); }
    std::cout << "islands: " << islands << '\n';
    return 0;
}

islands: 3

DFS goes as deep as possible before backtracking – here with recursion. It's used for connected components, cycle detection, topological sort and flood fill. For very deep graphs (10⁵+ nodes in a line), recursion can overflow the stack; use an explicit std::stack instead.

Dijkstra: weighted shortest paths

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> city{"Pune", "Mumbai", "Nashik", "Lonavala", "Satara"};
    int n = 5;
    std::vector<std::vector<std::pair<int, int>>> adj(n);      // (neighbour, km)
    auto road = [&](int u, int v, int w) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); };
    road(0, 3, 65); road(3, 1, 83); road(0, 2, 210); road(1, 2, 167); road(0, 4, 112);

    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> dist(n, INF);
    using State = std::pair<long long, int>;                    // (distance so far, node)
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;   // min heap
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                              // stale entry: skip
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int v = 1; v < n; v++) std::cout << "Pune -> " << city[v] << ": " << dist[v] << " km\n";
    return 0;
}

Pune -> Mumbai: 148 km
Pune -> Nashik: 210 km
Pune -> Lonavala: 65 km
Pune -> Satara: 112 km

Practice

Summary

Interview practice: graphs, BFS, DFS and shortest path questions.