BFS Breadth First Search on Graph in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for in graph traversal?

BFS stands for Breadth First Search. It is a method to explore all nodes of a graph level by level, starting from a chosen node.

beginner

In BFS, which data structure is primarily used to keep track of nodes to visit next?

A queue is used in BFS to keep track of nodes to visit next. It ensures nodes are explored in the order they are discovered.

intermediate

What is the main difference between BFS and DFS in graph traversal?

BFS explores nodes level by level using a queue, while DFS explores as deep as possible along each branch using a stack or recursion.

intermediate

What is the time complexity of BFS on a graph with V vertices and E edges?

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is processed once.

beginner

Why do we mark nodes as visited in BFS?

Marking nodes as visited prevents revisiting the same node multiple times, which avoids infinite loops and ensures correct traversal.

Which data structure does BFS use to keep track of nodes to visit?

A Priority Queue

B Stack

C Queue

D Hash Map

BFS uses a queue to explore nodes in the order they are discovered.

What is the first step in BFS traversal starting from a node?

A Add all neighbors to the queue

B Add the starting node to the queue and mark it visited

C Mark all nodes as visited

D Remove the starting node from the graph

BFS starts by adding the starting node to the queue and marking it visited.

What happens when BFS visits a node's neighbor that is already visited?

A It restarts the BFS

B It adds it to the queue again

C It removes the neighbor from the graph

D It skips adding it to the queue again

BFS skips neighbors already visited to avoid loops and repeated processing.

Which of these is a correct BFS traversal order for a graph starting at node 1 with neighbors 2 and 3?

A 1 -> 2 -> 3

B 1 -> 3 -> 2

C 2 -> 3 -> 1

D 3 -> 2 -> 1

BFS visits the starting node first, then its neighbors in the order they are discovered.

What is the space complexity of BFS in terms of vertices V?

A O(V)

B O(1)

C O(V^2)

D O(log V)

BFS requires space to store the queue and visited array, both proportional to the number of vertices.

Explain how BFS works step-by-step on a graph starting from a given node.

Think about how you explore friends in layers, starting from one person.

Describe why BFS is useful and what kind of problems it can solve.

Consider situations where you want to find the closest or all nodes reachable from a start.