TCS NQT Guide TCS NQT Coding Capability & AlgorithmsGraph Basics: Breadth-First Search (BFS) and Depth-First Search (DFS)

Graph Basics: Breadth-First Search (BFS) and Depth-First Search (DFS)

Learn core concepts, essential formulas, and attempt practice questions designed on the latest TCS NQT testing patterns.

Key Concepts & Formulas

1BFS: Traverses level-by-level. Uses a Queue. Ideal for shortest path on unweighted graphs.
2DFS: Traverses deep down branches. Uses a Stack (or recursion).

Practice Question 1

Which data structure is used to implement Breadth-First Search?

A) Queue

B) Stack

C) Tree

D) Heap

Correct Answer: A) Queue

Step-by-step Solution: BFS visits nodes level-by-level, utilizing a FIFO Queue to track frontier nodes.

Practice Question 2

What is time complexity of BFS on an adjacency list graph with V vertices and E edges?

A) O(V + E)

B) O(V * E)

C) O(V^2)

D) O(E^2)

Correct Answer: A) O(V + E)

Step-by-step Solution: BFS visits every vertex once and checks all outgoing edges. Time complexity is O(V + E).

Always maintain a boolean 'visited' array to prevent infinite loops in cyclic graphs.