BFS feels easy while the question only asks which data structure it uses. The real mistakes begin when the wording shifts to visit order, distance layers, non-tree edges, tree height or graph diameter. BFS problems can turn on the queue invariant or on applications where careless wording changes the answer; attempt each one before reading its explanation, write the queue after every dequeue, and label the source as level 0. The Coding & DSA Courses for Placements page places these BFS drills inside a wider graph and data-structure practice path.
BFS rules, queue order and distance layers
Breadth-first search uses a FIFO queue. Mark a vertex visited when it is enqueued, not dequeued, to prevent duplicate enqueues. Vertices leave the queue in nondecreasing shortest-path distance. In an unweighted graph, each BFS parent edge contributes to a shortest path.
With adjacency lists, BFS takes O(V + E) time and O(V) auxiliary space. Order within one level follows adjacency order, so a traversal need not be unique.
In the undirected graph V = {A, B, C, D, E, F, G}, E = {AB, AC, BD, BE, CF, EG, FG}, start at A and scan alphabetically:
After visiting | Queue |
|---|---|
Start |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Traversal is A, B, C, D, E, F, G; distances are 0, 1, 1, 2, 2, 2, 3; tree edges are AB, AC, BD, BE, CF, EG. The path A-B-E-G has length 3. Edge FG is not a tree edge because G was already discovered through E. Rebuild the trace with Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step if needed.
BFS MCQs 1-2: level order and the FIFO queue
Question 1
GATE 2004
Level order traversal of a rooted tree can be done by starting from the root and performing
(a) preorder traversal
(b) inorder traversal
(c) depth first search
(d) breadth first search
Answer: (d) breadth first search.
Level order visits distances 0, 1, then 2. FIFO makes BFS finish each level first; preorder and inorder may descend earlier.
Question 2
ISRO 2017
Which of the following data structure is useful in traversing a given graph by breadth first search?
(a) Stack
(b) List
(c) Queue
(d) None of the above.
Answer: (c) Queue.
Level-1 vertices must be processed before level 2. A queue preserves this frontier; a stack produces depth-first behaviour.
BFS MCQs 3-4: complexity and reachability
Question 3
NIACL AO IT Specialist 2025
What is the time complexity of BFS (Breadth-First Search) in terms of V (vertices) and E (edges)?
(a) O(VE)
(b) O(E log V)
(c) O(V²)
(d) O(V + E)
Answer: (d) O(V + E).
Each vertex is queued once, and all adjacency lists cost O(E) to scan. Total time is O(V + E); a matrix costs O(V²).
Question 4
NIACL AO IT Specialist 2025
Given two vertices in a graph s and t, which of the two traversals (BFS and DFS) can be used to find if there is a path from s to t?
(a) Only BFS
(b) Only DFS
(c) Both BFS and DFS
(d) Neither BFS nor DFS
Answer: (c) Both BFS and DFS.
Both visit every vertex reachable from s, so either finds t. BFS also minimises edges in an unweighted graph; DFS only proves reachability.
BFS MCQs 5-6: visit order and shortest paths
Question 5
GATE 2001
Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?
(a) d(r, u) < d(r, v)
(b) d(r, u) > d(r, v)
(c) d(r, u) ≤ d(r, v)
(d) None of the above
Answer: (c) d(r, u) ≤ d(r, v).
BFS completes distance k before k+1, so u cannot be farther than v. Equality is possible within one level.
Question 6
GATE 2014
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
(a) the shortest path between every pair of vertices.
(b) the shortest path from W to every vertex in the graph.
(c) the shortest paths from W to only those nodes that are leaves of T.
(d) the longest path in the graph.
Answer: (b) the shortest path from W to every vertex in the graph.
Each vertex enters through a parent one level closer to W. Parent pointers give d(W,x)-edge paths, but one BFS is not all-pairs.
BFS MCQs 7-8: non-tree edges, diameter and tree height
Question 7
GATE 2015
Let \(G = (V, E)\) be a simple undirected graph, and \(s\) be a particular vertex in it called the source. For \(x ∈ V\) , let \(d(x)\) denote the shortest distance in \(G\) from \(s\) to \(x\) . A breadth first search (BFS) is performed starting at \(s\). Let \(T\) be the resultant BFS tree. If \((u,v)\) is an edge of \(G\) that is not in \(T\) , then which one of the following CANNOT be the value of \(d(u) - d(v) \) ?
(a) -1
(b) 0
(c) 1
(d) 2
Answer: (d) 2.
Edge (u,v) gives d(u)≤d(v)+1 and the reverse, so |d(u)-d(v)|≤1. If d(v)=4, u may be at level 3, 4 or 5, never 6.
Question 8
GATE 2025
Let \(𝐺(𝑉, 𝐸)\) be an undirected and unweighted graph with 100 vertices. Let \(𝑑(𝑢, 𝑣)\) denote the number of edges in a shortest path between vertices \(u\) and \(v\) in \(V\) . Let the maximum value of \(𝑑(𝑢, 𝑣), 𝑢, 𝑣 ∈ 𝑉\) such that \(𝑢 ≠ 𝑣\) , be 30. Let \(T\) be any breadth-first search tree of \(G\) . Which ONE of the given options is CORRECT for every such graph \(G\) ?
(a) The height of \(T\) is exactly 15.
(b) The height of \(T\) is exactly 30.
(c) The height of \(T\) is at least 15.
(d) The height of \(T\) is at least 30.
Answer: (c) The height of \(T\) is at least 15.
A BFS tree's height from r is its eccentricity. Since 30≤d(u,r)+d(r,v) for diameter endpoints, one distance is at least 15; height need not equal 15 or 30.
BFS MCQs 9-10: graph applications and BFS versus DFS
Question 9
ISRO 2018
Which of the following is application of Breadth First Search on the graph?
(a) Finding diameter of the graph
(b) Finding bipartite graph
(c) Both (a) and (b)
(d) None of the above
Answer: (c) Both (a) and (b).
BFS alternates colours by level; a same-colour edge disproves bipartiteness. Repeating BFS from every vertex gives exact diameter; the two-BFS shortcut is guaranteed only for trees.
Question 10
GATE 2021
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
The value of ∣A−B∣ is _____________ .
This is a numerical-answer question.
Correct answer: 1.
With root-left-right DFS, A={r,a,b} and B={r,a,c}. Therefore A-B={b}, giving |A-B|=1.
BFS MCQs 11-12: maximum level position and BFS tree edges
Question 11
GATE 2016
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex \(t\) at a distance four from the root. If t is the \(n\)-th vertex in this BFS traversal, then the maximum possible value of \(n\) is _____________ .
This is a numerical-answer question.
Correct answer: 31.
Place t last on level 4 after filling earlier levels. Their sizes total 1+2+4+8+16=31, so the answer is 31, not 16.
Question 12
ISRO 2020
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
(a) v2v4
(b) v1v4
(c) v4v5
(d) v3v4
Answer: (b) v1v4.
Scanning v1 discovers v2,v3,v4, making its three incident edges tree edges. Later scans find v4 discovered; only v1v4 must be a tree edge.
BFS traps these questions expose and the next practice step
Trap | Questions | Deciding check |
|---|---|---|
Queue or stack | 1-2 | FIFO preserves the frontier. |
Representation and complexity | 3 | List: |
Reachability or shortest path | 4-6 | Both reach; BFS minimises edges. |
Non-tree edges | 7 |
|
Height and diameter | 8-9 | Eccentricity is at least half the diameter. |
Level counting and discovery | 10-12 | Sum levels; mark on enqueue. |
Under time pressure, mark the source as level 0 and mark vertices on enqueue. Write queue states, separate level order from within-level order, test each edge with |d(u)-d(v)| ≤ 1, and sum all levels in numerical answers.
Continue with Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE) for a broader graph set. If you want Data Structures arranged as a sequenced GATE route, use GATE Guidance by Sanchit Sir.
In short, BFS is queue-driven distance layering. See that invariant, and traversal, shortest-path, non-tree-edge and application questions stop looking like separate tricks.
