Network-protocols
September 3, 2024KVS 30-12-2018 Part-A
September 5, 2024GATE 2008
| Question 19 |
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
| MNOPQR | |
| NQMPOR | |
| QMNPRO | |
| QMNPOR |
Question 19 Explanation:
Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).
Correct Answer: C
Question 19 Explanation:
Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).