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

Recall & Review

beginner

What is the main idea behind using BFS to find the shortest path in an unweighted graph?

BFS explores nodes level by level, ensuring the first time we reach a node is via the shortest path from the start node.

beginner

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

A queue is used to keep nodes in the order they are discovered, ensuring level-wise traversal.

intermediate

How do we keep track of the shortest distance from the start node to every other node in BFS?

We maintain a distance array where distance[node] is updated the first time the node is visited, representing the shortest path length.

intermediate

Why does BFS guarantee the shortest path in an unweighted graph but not necessarily in a weighted graph?

Because BFS treats all edges as equal cost (1 step), it finds the minimum number of edges. Weighted graphs require algorithms like Dijkstra's to consider edge weights.

intermediate

What is the time complexity of BFS when finding the shortest path in an unweighted graph with V vertices and E edges?

The time complexity is O(V + E) because each vertex and edge is processed at most once.

Which data structure is essential for BFS to find the shortest path in an unweighted graph?

A Hash Map

B Stack

C Priority Queue

D Queue

BFS uses a queue to explore nodes level by level, which is key to finding the shortest path.

What does the distance array store in BFS shortest path algorithm?

A Weight of edges

B Number of edges from start node to each node

C Number of nodes in the graph

D Order of node discovery

The distance array stores the shortest number of edges from the start node to each node.

Why can't BFS be used directly to find shortest paths in weighted graphs?

A Because BFS does not consider edge weights

B Because BFS uses a stack

C Because BFS is too slow

D Because BFS only works on trees

BFS assumes all edges have equal weight, so it does not handle weighted edges correctly.

What is the initial distance value assigned to all nodes except the start node in BFS shortest path?

A 0

B 1

C -1 or Infinity

D Undefined

Nodes are initialized with -1 or Infinity to indicate they are not yet visited.

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

A O(V + E)

B O(V^2)

C O(E^2)

D O(log V)

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

Explain step-by-step how BFS finds the shortest path in an unweighted graph starting from a given node.

Think about how BFS explores neighbors and records distances.

Describe why BFS is suitable for shortest path in unweighted graphs but not for weighted graphs, and name an algorithm used for weighted graphs.

Compare edge treatment in BFS vs weighted graph algorithms.