Shortest Path in Unweighted Graph Using BFS in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for and what is its main use in graphs?

BFS stands for Breadth-First Search. It is mainly used to explore nodes level by level and find the shortest path in unweighted graphs.

beginner

Why is BFS suitable for finding the shortest path in an unweighted graph?

Because BFS explores neighbors in layers, the first time it reaches a node, it has found the shortest path to that node.

beginner

In BFS for shortest path, what data structure is commonly used to keep track of nodes to visit next?

A queue is used to keep track of nodes to visit next, ensuring nodes are processed in the order they are discovered.

intermediate

What additional information do we store during BFS to reconstruct the shortest path?

We store the parent or predecessor of each node, so after BFS finishes, we can trace back from the target node to the start node.

intermediate

What is the time complexity of BFS when finding the shortest path in an unweighted graph?

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

What data structure does BFS use to explore nodes in order?

A Queue

B Stack

C Priority Queue

D Hash Map

BFS uses a queue to explore nodes level by level.

In an unweighted graph, BFS finds the shortest path because it:

A Explores nodes in increasing order of distance from the start

B Explores nodes randomly

C Uses weights to calculate distance

D Only visits each node once

BFS explores nodes layer by layer, so the first time it reaches a node, it is via the shortest path.

Which of these is NOT needed to reconstruct the shortest path after BFS?

A Parent or predecessor of each node

B Node color coding

C Visited nodes set

D Distance from start node

Node color coding is not required for path reconstruction; parent tracking is essential.

What is the initial step in BFS for shortest path?

A Mark all nodes as visited

B Add all nodes to the queue

C Add the start node to the queue and mark it visited

D Calculate weights of edges

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

What is the time complexity of BFS in terms of vertices (V) and edges (E)?

A O(E^2)

B O(V^2)

C O(log V)

D O(V + E)

BFS visits each vertex and edge once, so time complexity is O(V + E).

Explain how BFS finds the shortest path in an unweighted graph step-by-step.

Think about how BFS explores nodes layer by layer.

Describe how to reconstruct the shortest path after BFS completes.

Trace back from the end node to the start using parents.