BFS- No of Teversals

Question

How to solve these kind of questions?

Comments

only first l.....just apply algorithmm...a see the valid sequence...

---

https://www.youtube.com/watch?v=QRq6p9s8NVg

Answer 1

By applying BFS algorithm

first we enter P in Queue and process it now we add neighbors of P that  are Q and R in any order, since all the options have Q as 2nd element first we enqueue Q then R

Queue have |R|Q|

now we process Q and add its neighbors

Queue have |T|R|

process R

queue have |S|M|T|

process T

Queue have |U|N|S|M|

now no new vertex will be added

so PQRTMSNU

Comments

How to eliminate other options?

How others are wrong?

---

@ Shubham Kumar Gupta

lets talk about second option....

start from P then according to BFS the nodes which must be viewed should be adjacent of P i.e QR....

but givewn is PQT..False/invalid sequence

---

you have to maintain tree like structure whenever there are more then one neighbors present.