حل تشریحی سوال شماره 45 دروس مشترک

فرض کنید در یک گراف همبند و بدون جهت G، الگوریتم جست‌و‌جوی سطح اول را با شروع از رأس r اجرا کنیم. فرض کنید u و v دو رأس دلخواه و متمایز G به‌غیر r باشند. همچنین فرض کنید d(r,u) و d(r,v) طول کوتاهترین مسیر از r به u و v باشند. اگر u قبل از v در جست‌وجوی سطح اول ملاقات شده باشد، کدام گزینه صحیح است؟