Notes › DSA
Graphs — BFS and DFS
A graph is a set of vertices (nodes) connected by edges. Maps, social networks, course prerequisites and grids are all graphs.
Terms
| Term | Meaning |
|---|---|
| Directed / undirected | edges have a direction (A → B) or not (A — B) |
| Weighted | each edge has a cost |
| Degree | number of edges at a vertex (in-degree / out-degree when directed) |
| Path / cycle | sequence of edges / a path that comes back to the start |
| Connected component | a group of vertices all reachable from each other |
| DAG | Directed Acyclic Graph — directed, no cycles (dependencies) |
| Tree | connected, undirected, no cycles: n vertices, n − 1 edges |
Representing a graph
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Memory | O(V + E) | O(V²) |
| Check edge u–v | O(degree) | O(1) |
| Best for | sparse graphs (most problems) | dense graphs, small V |
int n, m; cin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // skip for a directed graph
}
BFS — level by level
Uses a queue. The first time BFS reaches a node is by the fewest edges → shortest path in an unweighted graph.
vector<int> bfs(int src, vector<vector<int>>& adj) {
vector<int> dist(adj.size(), -1);
queue<int> q;
dist[src] = 0; q.push(src);
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); }
}
return dist; // -1 = unreachable
}
DFS — go deep, then back up
Uses recursion (or an explicit stack).
void dfs(int u, vector<vector<int>>& adj, vector<bool>& vis) {
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) dfs(v, adj, vis);
}
int countComponents(int n, vector<vector<int>>& adj) {
vector<bool> vis(n, false);
int comps = 0;
for (int i = 0; i < n; i++) if (!vis[i]) { dfs(i, adj, vis); comps++; }
return comps;
}
Both BFS and DFS are O(V + E).
| Use BFS for | Use DFS for |
|---|---|
| shortest path (unweighted), minimum steps | connectivity, components |
| level-by-level problems | cycle detection, topological sort |
| multi-source spread (rotting oranges) | paths/backtracking, islands |
Grids are graphs
Each cell is a node; its neighbours are up/down/left/right.
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
void flood(vector<vector<char>>& g, int r, int c) { // number of islands
if (r < 0 || c < 0 || r >= g.size() || c >= g[0].size() || g[r][c] != '1') return;
g[r][c] = '0'; // mark visited
for (int k = 0; k < 4; k++) flood(g, r + dr[k], c + dc[k]);
}
Cycle detection
- Undirected: during DFS, if you reach a visited node that is not your parent, there is a cycle. (Or union-find: an edge joining two nodes already in the same set.)
- Directed: keep a "currently on the recursion stack" array; reaching a node still on the stack means a cycle. (Or Kahn's algorithm: if not all nodes get processed, there is a cycle.)
Topological sort (DAG only)
An order where every edge u → v has u before v — e.g. course schedules, build order.
Kahn's algorithm (BFS with in-degrees):
vector<int> topo(int n, vector<vector<int>>& adj) {
vector<int> indeg(n, 0), order;
for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
return order; // order.size() < n → the graph has a cycle
}
Union-Find (Disjoint Set Union)
Answers "are u and v connected?" while edges are added, in almost O(1).
vector<int> parent, sz;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } // path compression
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false; // already connected → this edge makes a cycle
if (sz[a] < sz[b]) swap(a, b); // union by size
parent[b] = a; sz[a] += sz[b];
return true;
}
Used in Kruskal's MST, number of provinces, redundant connection, accounts merge.
Bipartite check
Colour nodes with 2 colours using BFS/DFS; if two neighbours get the same colour, the graph is not bipartite (it has an odd cycle).
Classic problems
| Problem | Tool |
|---|---|
| Number of islands / provinces | DFS/BFS or union-find |
| Rotting oranges | multi-source BFS |
| Shortest path in binary matrix | BFS |
| Clone graph | DFS + map |
| Course schedule I & II | topological sort |
| Detect cycle (directed/undirected) | DFS states / union-find |
| Is graph bipartite | BFS colouring |
| Word ladder | BFS on words |
Weighted shortest paths are in the next note: Shortest Paths and MST. Practise in the Graphs section.
Interview one-liners
- BFS = queue, DFS = stack/recursion; both O(V + E).
- BFS gives shortest paths only when all edges have the same weight.
- Topological order exists only for DAGs, and it may not be unique.
- Mark nodes visited when you push them in BFS, not when you pop, to avoid duplicates in the queue.