انجمنصفحه اولجستجوی انجمن

[setarehfb]

در جستجوی bfs یک گراف جهتدار در طبقه بندی یال ها در زمان پیمایش کدام نوع از یالها ب هیچ وجه ایجاد نمی شود؟؟ back tree cross forward
از دوستان کی میتونه لطف کنه و این سوال و نکتشو برام توضیح بده؟؟؟؟؟

[gunnersregister]

من اینجا جواب میدم ولی فک کنم باید سوال رو در مسیر دیگه ای مطرح میکرید:

ما به رئوس سه رنگ میدیم:
سفید: این راس اصلا ملاقات نشده.
خاکستری: این راس قبلا ملاقات شده.
سیاه: از این راس راهی برای ادامه نداریم و تموم فرزنداش قبلا بررسی شده اند.

Tree Edge: راس سفیدی که برای اولین بار اونو مشاهده میکنیم. الان این راس رو خاکستری میکنیم. این یال یال درختیه .

Back Edge: یال فرضی (U,V) که در پیمایش اونو ملاقات کنیم و در جنگل حاصل از این پیمایش U نواده V باشه.

Forward Edge: یال فرضی (U,V) که در پیمایش اونو ملاقات کنیم و در جنگل حاصل از این پیمایش V نواده U باشه.

Cross Edge: یالی که هیچکدوم از حالتهای بالا نباشه.

در پیمایش سطحی Forward Edge نداریم.

[setarehfb]

U نواده v باشه یعنی چی؟؟

[gunnersregister]

اگه زمان اولین ملاقات U زودتر از زمان اولین ملاقات V باشه و ارتباطی بین این دو تا از طریق یالها برقرار باشه اونوقت نود V نواده نود U هست.

[setarehfb]

یعنی در پیمایش از u به v بتونیم برسیم؟؟

[gunnersregister]

نه تنها از U به V برسیم بلکه نود U در این پیمایش زودتر از نود V ملاقات شده باشه.