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

Recall & Review

beginner

What does BFS stand for in graph traversal?

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

beginner

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

A queue is used in BFS to keep track of nodes to visit next. It helps explore nodes in the order they were discovered.

intermediate

What is the main difference between BFS and DFS (Depth First Search)?

BFS explores nodes level by level using a queue, while DFS explores as far as possible along one branch before backtracking, using a stack or recursion.

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 repeated work.

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), because it visits every vertex and edge at most once.

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

A Tree

B Queue

C Hash Map

D Stack

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

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

A Add all neighbors to the queue

B Remove the starting node from the graph

C Mark all nodes as visited

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

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 skips adding it to the queue again

B It adds it again to the queue

C It removes the neighbor from the graph

D It restarts the BFS

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

Which of these is NOT true about BFS?

A It uses a stack to keep track of nodes

B It can find the shortest path in an unweighted graph

C It explores nodes level by level

D It marks nodes as visited

BFS uses a queue, not a stack, to keep track of nodes.

What is the order of visiting nodes in BFS starting from node 1 in this graph? 1 connected to 2 and 3, 2 connected to 4

A 1, 4, 2, 3

B 1, 3, 2, 4

C 1, 2, 3, 4

D 4, 2, 3, 1

BFS visits neighbors level by level: start at 1, then 2 and 3, then 4.

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

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

Describe why BFS is useful for finding the shortest path in an unweighted graph.

Imagine walking through rooms one step at a time.