Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

More DSA notes