GATE 2017 CS (CS2) – Question 25

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

BFS is implemented using a queue. Which is a possible vertex-visiting order for the shown graph?

Diagram for GATE 2017 CS (CS2) question 25

MNOPQR
NQMPOR
QMNROP
POQNMR

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) POQNMR

Explanation

Start at P: its distance-one neighbours are O,Q and its distance-two vertices are N,M. R is reached from M at distance three. Choosing neighbour order O,Q and then N,M produces P,O,Q,N,M,R. This is D. The other sequences place a farther vertex before a nearer one or violate queue discovery order.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2012 CS (CS1) Q50 – For the shown directed weighted graph, several S-to-T shortest paths exist. Dijkstra…
GATE 2013 CS (CS1) Q29 – What is Bellman–Ford’s running time on a complete graph with n vertices?
GATE 2011 CS (CS1) Q64 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2011 CS (CS1) Q65 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2010 CS (CS1) Q60 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2010 CS (CS1) Q61 – The undirected graph on vertices 0,…,4 has weight matrix…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →