BFS and DFS

BFS explores neighbors layer by layer with a queue—shortest path in unweighted graphs. DFS goes deep first with stack/recursion—cycle detection, topological sort, connected components.

BFS skeleton

1. Enqueue start, mark visited
2. Dequeue u, process, enqueue unvisited neighbors
3. Track distance[] for shortest path layers

DFS skeleton

1. Mark visited, process node
2. Recurse on unvisited neighbors
3. Backtrack implicitly when returning

Backtracking preview

Backtracking is DFS with undo: choose, recurse, unchoose—used for subsets, permutations, and constraint puzzles (N-queens). Prune branches that violate constraints early.

BFS on small graph

#include 
#include 
#include 

int main() {
    std::vector> adj = {{1, 2}, {0, 3}, {0}, {1}};
    std::vector vis(4);
    std::queue q;
    q.push(0); vis[0] = true;
    std::cout << "BFS: ";
    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::cout << u << " ";
        for (int v : adj[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    std::cout << "\n";
    return 0;
}

Important interview questions and answers

1. Q: BFS vs DFS shortest path?
   A: BFS on unweighted graph finds shortest path; DFS does not guarantee shortest.
2. Q: Visited array why?
   A: Prevents infinite loops on cycles.

Self-check

1. What data structure does BFS use?
2. Time complexity BFS on V vertices E edges?

Tip: Always mark visited when enqueue/push—cycles cause infinite loops otherwise.