SyntaxPilot
Courses/C++/Lesson 37
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ · Lesson 37 of 40

DSA 2: graphs

queued

These are the notes for C++ episode 37, the second DSA episode. Places and the lanes between them don't fit in a list, so we invent the graph: vertices and edges. We store it first as an adjacency matrix (and see why it doesn't scale), then as an adjacency list; we crash a walk that goes round a cycle, fix it with visited marks (DFS), find the shortest route with BFS and a queue, and count connected components. Every program was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the SyntaxPilot compiler's command) and run; outputs are copied from those runs.

The problem: lanes, not a list

Raju delivers chai from Ravi's stall to six places. Narrow lanes join some of them. A vector<string> can hold the seven names, but the important information is who is joined to whom, and a list has nowhere to put it.

What is a graph

Think of a metro map:

Metro map Graph Here
a station a vertex (node) a place, numbered 0 to 6
a track between two stations an edge a lane
stations joined by a track neighbours (adjacent vertices) Market and Bank
trains both ways undirected edge every lane today
a one-way street directed edge (a → b only)
a ride that takes 4 minutes weighted edge (has a cost) every lane counts as 1 step today

Raju's map: 7 vertices, 8 edges.

 0 Stall ──── 1 School ──── 3 Temple ──── 5 Station
    │                          │              │
 2 Market ─────────────────────┘              │
    │                                         │
 4 Bank ──────────────── 6 Hospital ──────────┘

Edges: Stall–School, Stall–Market, School–Temple, Market–Temple, Market–Bank, Temple–Station, Bank–Hospital, Station–Hospital.

Graphs are everywhere: road maps, friends and followers, web pages and their links, courses and their prerequisites, flights between cities.

Storing a graph 1: the adjacency matrix

A table road[a][b] = 1 if a lane joins a and b. For a two-way lane, set both road[a][b] and road[b][a].

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

string place[7] = {"Stall", "School", "Market", "Temple", "Bank", "Station", "Hospital"};

int main() {
    int road[7][7] = {};                   // road[a][b] = 1: a lane joins a and b
    road[0][1] = road[1][0] = 1;           // Stall - School
    road[0][2] = road[2][0] = 1;           // Stall - Market
    road[2][4] = road[4][2] = 1;           // Market - Bank

    cout << "Lanes out of the Market:";
    for (int b = 0; b < 7; b++)
        if (road[2][b]) cout << " " << place[b];
    cout << endl;
    return 0;
}
Lanes out of the Market: Stall Bank

It works for 7 places. For the whole city:

#include <iostream>
using namespace std;

int main() {
    long long n = 100000;                  // junctions in the city
    long long cells = n * n;               // one cell per pair of junctions
    long long roads = n * 2;               // about 2 lanes per junction
    cout << "Table cells: " << cells << endl;
    cout << "Memory (int cells): " << cells * 4 / 1000000000 << " GB" << endl;
    cout << "Cells that are real roads: " << roads * 2 << endl;
    cout << "Wasted: " << 100.0 - 100.0 * roads * 2 / cells << " %" << endl;
    return 0;
}
Table cells: 10000000000
Memory (int cells): 40 GB
Cells that are real roads: 400000
Wasted: 99.996 %

A matrix stores every pair, even pairs with no lane, and listing one place's neighbours means scanning a whole row of n cells. Real maps are sparse: few edges per vertex.

Storing a graph 2: the adjacency list

Each place keeps only its own list of neighbours: a vector<vector<int>>, one inner vector per vertex.

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

vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);                // adj[a] = the places next to a

void road(int a, int b) {                  // a two-way lane
    adj[a].push_back(b);
    adj[b].push_back(a);
}

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    road(2, 4); road(3, 5); road(4, 6); road(5, 6);

    for (int a = 0; a < 7; a++) {
        cout << place[a] << ":";
        for (int b : adj[a]) cout << " " << place[b];
        cout << endl;
    }
    return 0;
}
Stall: School Market
School: Stall Temple
Market: Stall Temple Bank
Temple: School Market Station
Bank: Market Hospital
Station: Temple Hospital
Hospital: Bank Station
Adjacency matrix Adjacency list
Memory O(V²) O(V + E)
Is a–b an edge? O(1) O(number of a's neighbours)
List a's neighbours O(V) O(number of a's neighbours)
Use when small graphs, or most pairs joined (dense) almost always (sparse graphs)

V = number of vertices, E = number of edges. For a weighted graph, store pairs: vector<vector<pair<int,int>>> adj; with (neighbour, cost).

Walking the graph: the crash

"Can Raju reach the Hospital from the Stall?" The obvious recursive walk tries every lane from every place. (The first 12 steps are printed, with flush so they appear before the crash.)

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

vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }

int steps = 0;
bool canReach(int u, int target) {
    if (++steps <= 12) cout << " " << place[u] << flush;   // first 12 steps
    if (u == target) return true;
    for (int v : adj[u])                   // try every lane out of here
        if (canReach(v, target)) return true;
    return false;
}

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    road(2, 4); road(3, 5); road(4, 6); road(5, 6);
    cout << "Walk:";
    bool ok = canReach(0, 6);
    cout << endl << (ok ? "reachable" : "not reachable") << endl;
    return 0;
}
Walk: Stall School Stall School Stall School Stall School Stall School Stall School
Segmentation fault

The lanes are two-way: Stall → School → (School's first lane) Stall → School → … A loop in a graph is a cycle, and the walk goes round it forever. Each call waits for the next, the call stack fills up (stack overflow), and the program crashes.

In a maze, put a chalk mark on every room you enter and never enter a marked room. Go as deep as you can down one path, back up at a dead end, and try the next door.

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

vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }
vector<bool> visited(7, false);

bool canReach(int u, int target) {
    cout << " " << place[u];
    if (u == target) return true;
    visited[u] = true;                     // chalk mark: been here
    for (int v : adj[u])
        if (!visited[v] && canReach(v, target)) return true;
    return false;
}

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    road(2, 4); road(3, 5); road(4, 6); road(5, 6);
    cout << "Walk:";
    bool ok = canReach(0, 6);
    cout << endl << (ok ? "reachable" : "not reachable") << endl;
    return 0;
}
Walk: Stall School Temple Market Bank Hospital
reachable
  • visited[u] = true when we arrive; only walk to neighbours with !visited[v].
  • Each vertex is visited once and each edge is looked at twice (once from each end): O(V + E).
  • DFS finds a route (here 5 lanes), not necessarily the shortest.
  • Recursion uses the call stack; for very deep graphs (hundreds of thousands of vertices in a line) use an explicit stack<int> instead.

BFS: breadth-first search and the shortest path

A stone dropped in a pond makes rings: everything 1 step away first, then 2, then 3. Near things are reached before far things. A queue (first in, first out) gives exactly that order. The first time BFS reaches a place is along the fewest edges.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }
int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    road(2, 4); road(3, 5); road(4, 6); road(5, 6);
    vector<int> dist(7, -1), parent(7, -1);  // -1 = not reached yet
    queue<int> q; dist[0] = 0; q.push(0);    // start at the Stall
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {             // first time we reach v
                dist[v] = dist[u] + 1;
                parent[v] = u;               // we came to v from u
                q.push(v);
            }
    }
    for (int a = 0; a < 7; a++) cout << place[a] << ": " << dist[a] << endl;
    cout << "Route, backwards:";
    for (int v = 6; v != -1; v = parent[v]) cout << " " << place[v];
    cout << endl;
    return 0;
}
Stall: 0
School: 1
Market: 1
Temple: 2
Bank: 2
Station: 3
Hospital: 3
Route, backwards: Hospital Bank Market Stall
  • dist[v] == -1 means "not reached yet", so it is also the visited mark.
  • parent[v] = u remembers where we came from; following parent from the target back to the start gives the route, backwards.
  • BFS is O(V + E) and gives shortest paths when every edge costs the same. (With different costs, use Dijkstra's algorithm with a priority_queue.)

Route front to back with reverse:

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    road(2, 4); road(3, 5); road(4, 6); road(5, 6);
    vector<int> dist(7, -1), parent(7, -1);
    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) { dist[v] = dist[u] + 1; parent[v] = u; q.push(v); }
    }
    vector<int> path;
    for (int v = 6; v != -1; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());          // Hospital..Stall becomes Stall..Hospital
    cout << "Route (" << dist[6] << " lanes):";
    for (int v : path) cout << " " << place[v];
    cout << endl;
    return 0;
}
Route (3 lanes): Stall Market Bank Hospital

DFS or BFS?

DFS BFS
Uses recursion (or a stack) a queue
Order one path as deep as possible ring by ring, near before far
Good for reachability, connected components, cycles, mazes, topological order fewest steps, shortest route, nearest X, levels
Time O(V + E) O(V + E)

Connected components

After a flood only four lanes are left. A connected component is a piece of the graph where everyone can reach everyone. Run DFS from every place that no walk has reached yet; each start is a new component.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }
vector<bool> visited(7, false);

void explore(int u) {                      // DFS: mark everything reachable
    visited[u] = true;
    cout << " " << place[u];
    for (int v : adj[u])
        if (!visited[v]) explore(v);
}
int main() {
    road(0, 1); road(1, 3); road(2, 4); road(5, 6);   // lanes left after the flood
    int areas = 0;
    for (int a = 0; a < 7; a++) {
        if (!visited[a]) {                 // a place no walk has reached yet
            areas++; cout << "Area " << areas << ":";
            explore(a);
            cout << endl;
        }
    }
    cout << areas << " separate areas" << endl;
    return 0;
}
Area 1: Stall School Temple
Area 2: Market Bank
Area 3: Station Hospital
3 separate areas

Total time is still O(V + E): every vertex is explored exactly once across all the DFS calls.

Cheat sheet

Need Code
n vertices vector<vector<int>> adj(n);
Two-way edge adj[a].push_back(b); adj[b].push_back(a);
One-way edge adj[a].push_back(b);
Weighted edge vector<vector<pair<int,int>>> adj(n); adj[a].push_back({b, cost});
Visited marks vector<bool> visited(n, false);
DFS void dfs(int u) { visited[u] = true; for (int v : adj[u]) if (!visited[v]) dfs(v); }
BFS queue<int> q; dist[s] = 0; q.push(s); then pop, push unreached neighbours with dist[u] + 1
Route parent[v] = u; then follow parent back from the target
Components count the DFS calls started from unvisited vertices

Common mistakes

Mistake What you see Fix
Walking every lane with no visited marks Segmentation fault (the walk circles a cycle forever) vector<bool> visited; skip marked vertices
road(6, 7) with adj(7) Segmentation fault (vertices are 0..6, adj[7] doesn't exist) adj(n) for vertices 0..n-1; adj.at(7) would say vector::_M_range_check: __n (which is 7) >= this->size() (which is 7)
A two-way lane stored one way only no error; BFS from the Hospital prints Stall: -1 (unreachable) add both directions
A matrix for 100,000 junctions Memory (int cells): 40 GB adjacency list
Using DFS for "fewest steps" a 5-lane route when 3 lanes exist BFS
Marking visited only when a vertex is popped in BFS the same vertex is pushed many times (slow, wrong parent) mark (set dist) when you push

Mini project: count the islands

A grid of 1 (land) and 0 (water). Each land cell is a vertex, joined to the land cells above, below, left and right. Count the islands (connected components):

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

vector<string> grid = {
    "11000",
    "11010",
    "00011",
    "10000",
    "10011"};
int R = 5, C = 5;

void sink(int r, int c) {                       // DFS: mark a whole island as seen
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != '1') return;
    grid[r][c] = '0';                           // 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 < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == '1') { islands++; sink(r, c); }
    cout << islands << " islands" << endl;
    return 0;
}
4 islands

Here the grid itself is the graph: the neighbours are computed (r±1, c±1) instead of stored, and turning a 1 into 0 is the visited mark.

Practice

  1. Draw your own area as a graph (at least 6 places), and code it as an adjacency list.
  2. Print Raju's route front to back with reverse.
  3. Make the Market–Bank and Bank–Hospital lanes one-way (Market → Bank, Hospital → Bank). Run BFS from the Bank: who can't be reached?
  4. Count the islands in a grid of 0s and 1s (the mini project).
Solutions

Exercise 2: route.cpp above.

Exercise 3:

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

vector<string> place = {"Stall", "School", "Market", "Temple",
                         "Bank", "Station", "Hospital"};
vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }
void oneWay(int a, int b) { adj[a].push_back(b); }      // only a -> b

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3);
    oneWay(2, 4); road(3, 5); oneWay(6, 4); road(5, 6);  // Market -> Bank, Hospital -> Bank
    vector<int> dist(7, -1);
    queue<int> q;
    dist[4] = 0; q.push(4);                     // BFS from the Bank
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    for (int a = 0; a < 7; a++)
        cout << place[a] << ": " << (dist[a] == -1 ? string("can't reach") : to_string(dist[a])) << endl;
    return 0;
}
Stall: can't reach
School: can't reach
Market: can't reach
Temple: can't reach
Bank: 0
Station: can't reach
Hospital: can't reach

Both of the Bank's lanes now only lead into it, so nothing can be reached from it. In a directed graph, "a can reach b" doesn't mean "b can reach a".

Exercise 4: islands.cpp above.

Quick quiz

Lanes: 0–1, 0–2, 1–3, 2–3, 3–4. BFS from vertex 0, neighbours in the order added. What is dist[4]?

Answer

3. Ring 1: vertices 1 and 2. Ring 2: vertex 3 (reached from 1 first). Ring 3: vertex 4. The program prints 3:

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

vector<vector<int>> adj(7);
void road(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); }

int main() {
    road(0, 1); road(0, 2); road(1, 3); road(2, 3); road(3, 4);
    vector<int> dist(7, -1);
    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) { dist[v] = dist[u] + 1; q.push(v); }
    }
    cout << dist[4] << endl;
    return 0;
}

Interview questions

  1. What is a graph? A set of vertices and a set of edges between pairs of them; directed or undirected, weighted or not.
  2. Adjacency list vs matrix? List: O(V + E) memory, best for sparse graphs. Matrix: O(V²) memory, O(1) edge check, for small or dense graphs.
  3. BFS vs DFS? BFS (queue) explores level by level and gives shortest paths in unweighted graphs; DFS (recursion/stack) goes deep and suits reachability, components and cycle detection. Both O(V + E).
  4. Why do you need a visited array? Graphs can have cycles; without it a traversal revisits vertices forever.
  5. How do you get the actual shortest path, not only its length? Store parent[v] when v is first reached, then follow parents back from the target.
  6. How do you count connected components? Start a DFS/BFS from every unvisited vertex; the number of starts is the number of components.
  7. Shortest path with different edge costs? Dijkstra's algorithm (non-negative costs) with a priority queue: O((V + E) log V).
  8. Number of islands? Treat land cells as vertices joined to adjacent land cells; count components with DFS/BFS.

Glossary

Term Meaning, with an example
graph Vertices plus the edges between them: Raju's map.
vertex (node) One thing in the graph: the Market, vertex 2.
edge A link between two vertices: the Market–Bank lane.
neighbour (adjacent) A vertex joined to another by an edge.
undirected graph Edges work both ways (two-way lanes).
directed graph Edges go one way (one-way streets, followers).
weighted graph Each edge has a cost (minutes, km).
degree How many edges touch a vertex: the Market has 3.
path A sequence of vertices joined by edges: Stall, Market, Bank, Hospital.
cycle A path that comes back to where it started: Stall, School, Temple, Market, Stall.
sparse / dense Few edges compared to V² / most pairs joined.
adjacency matrix A V × V table: road[a][b] is 1 if a and b are joined.
adjacency list For each vertex, the list of its neighbours: vector<vector<int>>.
traversal Visiting every reachable vertex in some order.
visited A mark that a vertex has already been seen.
DFS (depth-first search) Go as deep as possible, then back up; uses recursion or a stack.
BFS (breadth-first search) Explore ring by ring from the start; uses a queue.
queue First in, first out (<queue>, episode 25).
shortest path The route with the fewest edges (or least total cost).
dist Distance in edges from the start; -1 = not reached.
parent The vertex we came from; used to rebuild the route.
connected component A piece of the graph in which every vertex can reach every other.
stack overflow The call stack runs out of space, usually from endless recursion: a segmentation fault.
O(V + E) Time proportional to vertices plus edges: one look at each.

Summary

  • A graph is vertices and edges: undirected, directed or weighted.
  • Store it as an adjacency list, vector<vector<int>> adj(n); a matrix only for small, dense graphs.
  • Graphs have cycles: always keep visited marks.
  • DFS (recursion) goes deep: reachability and connected components.
  • BFS (queue) goes ring by ring: fewest steps, with parent to rebuild the route.
  • Both are O(V + E).

Next episode: some problems ask the same small question millions of times. DSA 3: dynamic programming.