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.
DFS: depth-first search
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] = truewhen 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] == -1means "not reached yet", so it is also the visited mark.parent[v] = uremembers where we came from; followingparentfrom 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
- Draw your own area as a graph (at least 6 places), and code it as an adjacency list.
- Print Raju's route front to back with
reverse. - Make the Market–Bank and Bank–Hospital lanes one-way (Market → Bank, Hospital → Bank). Run BFS from the Bank: who can't be reached?
- 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
- What is a graph? A set of vertices and a set of edges between pairs of them; directed or undirected, weighted or not.
- 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.
- 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).
- Why do you need a visited array? Graphs can have cycles; without it a traversal revisits vertices forever.
- 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. - How do you count connected components? Start a DFS/BFS from every unvisited vertex; the number of starts is the number of components.
- Shortest path with different edge costs? Dijkstra's algorithm (non-negative costs) with a priority queue: O((V + E) log V).
- 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
parentto rebuild the route. - Both are O(V + E).
Next episode: some problems ask the same small question millions of times. DSA 3: dynamic programming.