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