Graph Traversal

BFS and DFS for traversing graphs

Graph Traversal

Graph Traversal is the process of visiting all vertices in a graph. There are two main methods: BFS and DFS.

Breadth-First Search (BFS)

Visits vertices by “level of depth” using a Queue.

Algorithm

Start from source vertex, add to queue
Remove vertex from queue
Visit unvisited neighbors, add to queue
Repeat until queue is empty

Implementation

void bfs(int start) {
    vector<bool> visited(n + 1, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        cout << u << " "; // Process vertex
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

BFS for Shortest Path (Unweighted)

vector<int> bfsShortestPath(int start) {
    vector<int> dist(n + 1, -1);
    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);
            }
        }
    }
    
    return dist;
}

BFS for Finding Path

vector<int> bfsPath(int start, int end) {
    vector<int> parent(n + 1, -1);
    queue<int> q;
    
    q.push(start);
    parent[start] = start;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (u == end) break;
        
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    // Reconstruct path
    if (parent[end] == -1) return {}; // No path
    
    vector<int> path;
    for (int v = end; v != start; v = parent[v]) {
        path.push_back(v);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    
    return path;
}

Complexity

Time: $O(V + E)$
Space: $O(V)$

Depth-First Search (DFS)

Visits vertices by going “as deep as possible” first, then backtracks.

Recursive DFS

vector<bool> visited;

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

// Usage
visited.assign(n + 1, false);
dfs(1);

Iterative DFS (Using Stack)

void dfsIterative(int start) {
    vector<bool> visited(n + 1, false);
    stack<int> st;
    
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        cout << u << " "; // Process vertex
        
        // Push in reverse order to maintain left-to-right order
        for (int i = adj[u].size() - 1; i >= 0; i--) {
            int v = adj[u][i];
            if (!visited[v]) {
                st.push(v);
            }
        }
    }
}

DFS Applications

1. Cycle Detection

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

// Directed Graph
vector<int> color; // 0: white, 1: gray, 2: black

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

2. Topological Sort

vector<int> order;
vector<bool> visited;

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

vector<int> topologicalSort() {
    visited.assign(n + 1, false);
    order.clear();
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfsTopSort(i);
        }
    }
    
    reverse(order.begin(), order.end());
    return order;
}

3. Count Connected Components

int countComponents() {
    visited.assign(n + 1, false);
    int count = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }
    
    return count;
}

4. Finding Bridges (Critical Edges)

vector<int> disc, low;
vector<pair<int, int>> bridges;
int timer = 0;

void dfsBridge(int u, int parent) {
    disc[u] = low[u] = timer++;
    
    for (int v : adj[u]) {
        if (disc[v] == -1) { // Not visited yet
            dfsBridge(v, u);
            low[u] = min(low[u], low[v]);
            
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void findBridges() {
    disc.assign(n + 1, -1);
    low.assign(n + 1, -1);
    
    for (int i = 1; i <= n; i++) {
        if (disc[i] == -1) {
            dfsBridge(i, -1);
        }
    }
}

Complexity

Time: $O(V + E)$
Space: $O(V)$ (Stack space for recursion)

BFS vs DFS

Property	BFS	DFS
Data Structure	Queue	Stack/Recursion
Memory	$O(V)$ or more	$O(h)$ where h = depth
Shortest Path	Yes (unweighted)	No
Cycle Detection	Yes	Yes
Topological Sort	Yes (Kahn’s)	Yes
Connected Components	Yes	Yes

0-1 BFS

For graphs with edge weights of 0 or 1, use deque instead of priority queue.

vector<int> bfs01(int start) {
    vector<int> dist(n + 1, INF);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (w == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }
    
    return dist;
}

Complexity: $O(V + E)$

Multi-Source BFS

BFS from multiple sources simultaneously.

vector<int> multiSourceBFS(vector<int>& sources) {
    vector<int> dist(n + 1, INF);
    queue<int> q;
    
    for (int s : sources) {
        dist[s] = 0;
        q.push(s);
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    return dist;
}

Example Problems

Problem: Grid BFS (Maze)

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

int bfsMaze(vector<string>& grid, int sr, int sc, int er, int ec) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> q;
    
    q.push({sr, sc});
    dist[sr][sc] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == er && y == ec) return dist[x][y];
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols 
                && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1; // No path
}

Summary

Algorithm	Use Case
BFS	Shortest path (unweighted), Level-order
DFS	Cycle detection, Topological sort, Connected components
0-1 BFS	Shortest path (0-1 weights)
Multi-Source BFS	Distance from multiple sources

💡 Tip: If you need shortest path in an unweighted graph, always use BFS.