در جستجوی bfs یک گراف جهتدار در طبقه بندی یال ها در زمان پیمایش کدام نوع از یالها ب هیچ وجه ایجاد نمی شود؟؟ back tree cross forward
از دوستان کی میتونه لطف کنه و این سوال و نکتشو برام توضیح بده؟؟؟؟؟
من اینجا جواب میدم ولی فک کنم باید سوال رو در مسیر دیگه ای مطرح میکرید:
ما به رئوس سه رنگ میدیم:
سفید: این راس اصلا ملاقات نشده.
خاکستری: این راس قبلا ملاقات شده.
سیاه: از این راس راهی برای ادامه نداریم و تموم فرزنداش قبلا بررسی شده اند.
Tree Edge: راس سفیدی که برای اولین بار اونو مشاهده میکنیم. الان این راس رو خاکستری میکنیم. این یال یال درختیه .
Back Edge: یال فرضی (U,V) که در پیمایش اونو ملاقات کنیم و در جنگل حاصل از این پیمایش U نواده V باشه.
Forward Edge: یال فرضی (U,V) که در پیمایش اونو ملاقات کنیم و در جنگل حاصل از این پیمایش V نواده U باشه.
Cross Edge: یالی که هیچکدوم از حالتهای بالا نباشه.
در پیمایش سطحی Forward Edge نداریم.
U نواده v باشه یعنی چی؟؟
اگه زمان اولین ملاقات U زودتر از زمان اولین ملاقات V باشه و ارتباطی بین این دو تا از طریق یالها برقرار باشه اونوقت نود V نواده نود U هست.
یعنی در پیمایش از u به v بتونیم برسیم؟؟
نه تنها از U به V برسیم بلکه نود U در این پیمایش زودتر از نود V ملاقات شده باشه.