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
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2014 Set 2 · Q14
MCQ1 markEasy
Time
Consider the tree arcs of a BFS traversal from a source node in an unweighted, connected, undirected graph. The tree formed by the tree arcs is a data structure for computing
Select one answerSingle correct
Pick an option to check
Solution
Step-by-step verified solution
Official answer: B) the shortest path from W to every vertex in the graph.
Graph TraversalsBreadth-First Search (BFS) explores vertices level by level in increasing order of their distance from the source vertex .
In an unweighted graph, the tree arcs of a BFS traversal from form a BFS tree , which contains the shortest path (in terms of minimum number of edges) from the root to every reachable vertex in the graph.
Hence, the BFS tree serves as a data structure to compute the shortest path from to every vertex in the graph, making (B) the correct option.
Try the question first, then check your work.
Examiner trap
The misconception this question tests
Recall that BFS on an unweighted graph finds the minimum number of edges from the source to every other reachable vertex.
This Graph Traversals previous year question is Q14 of the GATE CSE 2014 Set 2 paper. Find more GATE CSE PYQs on Graph Traversals in Algorithms, or browse all GATE CSE PYQs.
Free diagnostic
Where do you stand for GATE?
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Traversals PYQs now with no account.
One GATE CSE PYQ every morning
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Graph Traversals in GATE CSE
Graph Traversals has 16 GATE CSE PYQs across 12 papers from 2014 to 2026. 5 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2014 Set 2.
How GATE tests Graph TraversalsMore from GATE CSE 2014 Set 2
- Q16Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?MCQ1 markMedium
- Q12A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7…MCQ1 markEasy
- Q17Consider the grammar defined by the following production rules, with two operators * and + S → T * P T → U T * U P → Q + P Q Q → Id U → Id Which one of the fol…MCQ1 markEasy
- Q11Suppose n and p are unsigned int variables in a C program. We wish to set p to nC3. If n is large, which one of the following statements is most likely to set…MCQ1 markMedium
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.