Chapter 21 of 30

Graph Representation, DFS & BFS

Master graph representation, depth-first search, breadth-first search, connected components, and grid traversal.

Graph TerminologyGraph RepresentationDFS on GraphsBFS on GraphsConnected ComponentsGrid Traversal

Graph Representation, DFS & BFS

Graphs model relationships: roads between cities, dependencies between tasks, friendships in a network. DFS and BFS are the two fundamental ways to explore them.

Graph Terminology

Vertex (node): a point in the graph
Edge: a connection between two vertices
Directed: edges have direction (A → B)
Undirected: edges go both ways (A — B)
Weighted: edges have associated costs
Degree: number of edges connected to a vertex
Path: sequence of vertices connected by edges
Cycle: a path that starts and ends at the same vertex
Connected: every vertex can reach every other vertex

Graph Representation

Adjacency Matrix

hljs cpp

int adj[100][100] = {};  // adj[u][v] = 1 if edge exists

// Add edge
adj[u][v] = 1;
adj[v][u] = 1;  // undirected

// Check edge
if (adj[u][v]) { ... }

O(1) edge check, but O(n²) space. Use for dense graphs.

Adjacency List (Preferred)

hljs cpp

vector<vector<int>> adj(n);

// Add edge
adj[u].push_back(v);
adj[v].push_back(u);  // undirected

// Iterate neighbors
for (int v : adj[u]) { ... }

O(degree) per operation, O(n + m) space. Use for sparse graphs.

Weighted Edges

hljs cpp

vector<vector<pair<int,int>>> adj(n);  // {neighbor, weight}

adj[u].push_back({v, w});
adj[v].push_back({u, w});

DFS on Graphs

DFS explores as deep as possible before backtracking:

hljs cpp

vector<bool> visited(n, false);

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

Iterative DFS (Avoids Stack Overflow)

hljs cpp

stack<int> st;
vector<bool> visited(n, false);

st.push(source);
while (!st.empty()) {
    int u = st.top(); st.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) st.push(v);
    }
}

DFS Applications

Cycle detection: track parent and check for back edges
Topological sort: DFS with post-order
Connected components: run DFS from each unvisited node
Bipartite checking: 2-color during DFS
Finding bridges and articulation points: Tarjan's algorithm

BFS on Graphs

BFS explores level by level (closest nodes first):

hljs cpp

queue<int> q;
vector<bool> visited(n, false);
vector<int> dist(n, -1);

q.push(source);
visited[source] = true;
dist[source] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

BFS Applications

Shortest path in unweighted graphs: BFS gives minimum distance
Level-order traversal: process nodes level by level
Minimum number of moves: knight moves, coin changes
Connected components: same as DFS but level-by-level

Connected Components

hljs cpp

vector<bool> visited(n, false);
int components = 0;

for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        components++;
        dfs(i);  // or bfs(i)
    }
}
cout << components << "\n";

Component Sizes

hljs cpp

int dfs(int u) {
    visited[u] = true;
    int size = 1;
    for (int v : adj[u]) {
        if (!visited[v]) size += dfs(v);
    }
    return size;
}

Grid Traversal

Grids are implicit graphs: each cell is a vertex, edges connect adjacent cells.

hljs cpp

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void bfs(vector<vector<int>> &grid, int sr, int sc) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int,int>> q;
    
    q.push({sr, sc});
    visited[sr][sc] = true;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

Number of Islands (Classic)

hljs cpp

int numIslands(vector<vector<char>> &grid) {
    int n = grid.size(), m = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                count++;
                bfs(grid, i, j);  // mark entire island
            }
        }
    }
    return count;
}

Summary

Adjacency list is the standard representation (space-efficient for sparse graphs)
DFS: deep exploration, uses stack (recursive or iterative)
BFS: level-by-level, uses queue, gives shortest paths in unweighted graphs
Grid traversal: use dx/dy arrays for 4-directional movement
Both DFS and BFS are O(n + m) where n = vertices, m = edges

Ch 20: Coordinate Compression, Fenwick Tree & Segment Tree Ch 22: Cycle Detection, Bipartite Checking & Topological Sort

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 21 of 30

Graph Representation, DFS & BFS

Master graph representation, depth-first search, breadth-first search, connected components, and grid traversal.

Graph TerminologyGraph RepresentationDFS on GraphsBFS on GraphsConnected ComponentsGrid Traversal

Graph Representation, DFS & BFS

Graphs model relationships: roads between cities, dependencies between tasks, friendships in a network. DFS and BFS are the two fundamental ways to explore them.

Graph Terminology

Vertex (node): a point in the graph
Edge: a connection between two vertices
Directed: edges have direction (A → B)
Undirected: edges go both ways (A — B)
Weighted: edges have associated costs
Degree: number of edges connected to a vertex
Path: sequence of vertices connected by edges
Cycle: a path that starts and ends at the same vertex
Connected: every vertex can reach every other vertex

Graph Representation

Adjacency Matrix

hljs cpp

int adj[100][100] = {};  // adj[u][v] = 1 if edge exists

// Add edge
adj[u][v] = 1;
adj[v][u] = 1;  // undirected

// Check edge
if (adj[u][v]) { ... }

O(1) edge check, but O(n²) space. Use for dense graphs.

Adjacency List (Preferred)

hljs cpp

vector<vector<int>> adj(n);

// Add edge
adj[u].push_back(v);
adj[v].push_back(u);  // undirected

// Iterate neighbors
for (int v : adj[u]) { ... }

O(degree) per operation, O(n + m) space. Use for sparse graphs.

Weighted Edges

hljs cpp

vector<vector<pair<int,int>>> adj(n);  // {neighbor, weight}

adj[u].push_back({v, w});
adj[v].push_back({u, w});

DFS on Graphs

DFS explores as deep as possible before backtracking:

hljs cpp

vector<bool> visited(n, false);

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

Iterative DFS (Avoids Stack Overflow)

hljs cpp

stack<int> st;
vector<bool> visited(n, false);

st.push(source);
while (!st.empty()) {
    int u = st.top(); st.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) st.push(v);
    }
}

DFS Applications

Cycle detection: track parent and check for back edges
Topological sort: DFS with post-order
Connected components: run DFS from each unvisited node
Bipartite checking: 2-color during DFS
Finding bridges and articulation points: Tarjan's algorithm

BFS on Graphs

BFS explores level by level (closest nodes first):

hljs cpp

queue<int> q;
vector<bool> visited(n, false);
vector<int> dist(n, -1);

q.push(source);
visited[source] = true;
dist[source] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

BFS Applications

Shortest path in unweighted graphs: BFS gives minimum distance
Level-order traversal: process nodes level by level
Minimum number of moves: knight moves, coin changes
Connected components: same as DFS but level-by-level

Connected Components

hljs cpp

vector<bool> visited(n, false);
int components = 0;

for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        components++;
        dfs(i);  // or bfs(i)
    }
}
cout << components << "\n";

Component Sizes

hljs cpp

int dfs(int u) {
    visited[u] = true;
    int size = 1;
    for (int v : adj[u]) {
        if (!visited[v]) size += dfs(v);
    }
    return size;
}

Grid Traversal

Grids are implicit graphs: each cell is a vertex, edges connect adjacent cells.

hljs cpp

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void bfs(vector<vector<int>> &grid, int sr, int sc) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int,int>> q;
    
    q.push({sr, sc});
    visited[sr][sc] = true;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

Number of Islands (Classic)

hljs cpp

int numIslands(vector<vector<char>> &grid) {
    int n = grid.size(), m = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                count++;
                bfs(grid, i, j);  // mark entire island
            }
        }
    }
    return count;
}

Summary

Adjacency list is the standard representation (space-efficient for sparse graphs)
DFS: deep exploration, uses stack (recursive or iterative)
BFS: level-by-level, uses queue, gives shortest paths in unweighted graphs
Grid traversal: use dx/dy arrays for 4-directional movement
Both DFS and BFS are O(n + m) where n = vertices, m = edges

Ch 20: Coordinate Compression, Fenwick Tree & Segment Tree Ch 22: Cycle Detection, Bipartite Checking & Topological Sort

Prefer reading offline? Download the full book as a PDF.

Download Free Book