Skip to main content

​
Graph Fundamentals

DFS vs BFS Graph Traversal

​
The Mental Model

Graphs model relationships. Cities connected by roads, friends in a social network, dependencies between tasks—all graphs. Mastering graphs means learning to see problems as nodes and edges, then applying the right traversal or algorithm.
Pattern Recognition Signals:
  • “Connected components” → DFS/BFS + Union-Find
  • “Shortest path” → BFS (unweighted) or Dijkstra (weighted)
  • “Cycle detection” → DFS with colors
  • “Topological ordering” → Kahn’s algorithm or DFS
  • “Bipartite check” → BFS/DFS coloring

​
Graph Representations

​
Adjacency List (Most Common in CP)

// Unweighted graph
int n, m;  // n nodes, m edges
vector<vector<int>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);  // Remove for directed graph
}

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

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

​
Edge List (For Kruskal’s MST)

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
    cin >> edges[i].u >> edges[i].v >> edges[i].w;
}

​
Adjacency Matrix (Dense Graphs, Floyd-Warshall)

vector<vector<int>> adj(n + 1, vector<int>(n + 1, INF));
for (int i = 1; i <= n; i++) adj[i][i] = 0;

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u][v] = min(adj[u][v], w);
}
DFS explores as deep as possible before backtracking. It’s the foundation for many graph algorithms. 
vector<bool> visited(n + 1, false);

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

// Usage
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
        // Found a new connected component
    }
}

​
Iterative DFS (Avoids Stack Overflow)

void dfs(int start) {
    stack<int> st;
    st.push(start);
    
    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);
            }
        }
    }
}
BFS explores all neighbors before going deeper. BFS finds shortest path in unweighted graphs. 
vector<int> dist(n + 1, -1);

void bfs(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 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);
            }
        }
    }
}

​
BFS on Grid

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

int bfs(vector<vector<int>>& grid, int sr, int sc, int tr, int tc) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    
    queue<pair<int, int>> q;
    q.push({sr, sc});
    dist[sr][sc] = 0;
    
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        
        if (r == tr && c == tc) return dist[r][c];
        
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            
            if (nr >= 0 && nr < n && nc >= 0 && nc < m 
                && grid[nr][nc] == 0 && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    
    return -1;  // Unreachable
}

​
Pattern 1: Connected Components

Problem: Count connected components or check if two nodes are connected. 
int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n + 1, false);
    int components = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);  // or bfs(i)
            components++;
        }
    }
    
    return components;
}
Codeforces Problems:
ProblemRatingLink
Building Roads1200CSES
Connected Components1000CF 977E

​
Pattern 2: Cycle Detection

​
In Undirected Graph

bool hasCycle(int u, int parent) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u)) return true;
        } else if (v != parent) {
            return true;  // Back edge found
        }
    }
    
    return false;
}

​
In Directed Graph (Using Colors)

// 0 = white (unvisited), 1 = gray (in progress), 2 = black (done)
vector<int> color(n + 1, 0);

bool hasCycle(int u) {
    color[u] = 1;
    
    for (int v : adj[u]) {
        if (color[v] == 1) return true;    // Back edge
        if (color[v] == 0 && hasCycle(v)) return true;
    }
    
    color[u] = 2;
    return false;
}

​
Pattern 3: Topological Sort

Problem: Order nodes so all edges go from earlier to later.

​
Kahn’s Algorithm (BFS)

vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> inDegree(n + 1, 0);
    
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    if (order.size() != n) return {};  // Cycle exists
    return order;
}

​
DFS Approach

vector<int> order;
vector<bool> visited(n + 1, false);

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
    order.push_back(u);
}

// After all DFS calls
reverse(order.begin(), order.end());
Codeforces Problems:
ProblemRatingLink
Course Schedule1300CSES
Fox and Names1500CF 510C

​
Pattern 4: Bipartite Check

Problem: Can we 2-color the graph such that no edge connects same colors? 
bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n + 1, -1);
    
    for (int start = 1; start <= n; start++) {
        if (color[start] != -1) continue;
        
        queue<int> q;
        q.push(start);
        color[start] = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
    }
    
    return true;
}
Key Insight: A graph is bipartite iff it has no odd-length cycles.

​
Pattern 5: Flood Fill

Problem: Find connected regions in a grid (like paint bucket tool). 
void floodFill(vector<vector<int>>& grid, int r, int c, int newColor) {
    int oldColor = grid[r][c];
    if (oldColor == newColor) return;
    
    int n = grid.size(), m = grid[0].size();
    
    queue<pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = newColor;
    
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    
    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 
                && grid[nx][ny] == oldColor) {
                grid[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
}

​
Common Mistakes

Mistake 1: 0 vs 1 Indexing Be consistent. In CP, 1-indexing is common for graphs.
vector<vector<int>> adj(n + 1);  // 1 to n
Mistake 2: Forgetting to Check All Components Not all nodes may be reachable from node 1:
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
    }
}
Mistake 3: Stack Overflow in DFS For graphs with 10^5+ nodes, use iterative DFS or increase stack size.
Mistake 4: Revisiting in BFS Mark visited when pushing to queue, not when popping:
// WRONG
int u = q.front(); q.pop();
if (visited[u]) continue;
visited[u] = true;

// CORRECT
for (int v : adj[u]) {
    if (!visited[v]) {
        visited[v] = true;  // Mark here
        q.push(v);
    }
}

​
Practice Problems

​
Beginner (1000-1200)

ProblemPatternLink
Counting RoomsFlood fillCSES
Building RoadsComponentsCSES
LabyrinthBFS pathCSES

​
Intermediate (1200-1500)

ProblemPatternLink
Course ScheduleTopologicalCSES
Round TripCycle findingCSES
Building TeamsBipartiteCSES

​
Advanced (1500-1700)

ProblemPatternLink
Flight RoutesMulti-BFSCSES
Game RoutesDP on DAGCSES
Longest PathDAG DPCSES

​
Key Takeaways

DFS for Exploration

Use DFS for connectivity, cycles, and backtracking problems.

BFS for Shortest

BFS gives shortest path in unweighted graphs.

Adjacency List

Default representation in CP. O(V + E) space.

Color for State

Track visited/processing/done states for cycle detection.

​
Next Up

Chapter 14: Shortest Paths

Master Dijkstra, Bellman-Ford, and Floyd-Warshall for weighted shortest paths.