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

[فاطمه رنجبر]

سلام دوستان میشه بگید یال درختی وپشتی وپیشرووعبوری روچطوری باید تشخیص بدیم؟

[happy07]

سلام
ما چهار نوع یال داریم:
یال درختی: به یال‌های درخت گفته می‌شه.
یال پیشرو: بین یه نود و یکی از نوادگانش رسم می‌شه.
یال پشتی: بین یه نود و یکی از اجدادش رسم می‌شه.
یال عبوری: یالی که هیچ کدوم از اینها نباشه.

برای تشخیص اینکه یال جز کدوم دسته است کافیه شما درخت رو با هر روشی که دوست دارید بکشید، یال‌های گراف که در درخت هستند یال‌های درختی هستند. بقیه‌ی یال‌های گراف، که در درخت نیستند رو یکی یکی بررسی کنید ببینید بین یک راس از درخت رسم شده با یک نواده‌اش که در این صورت می‌شه یال پیشرو، یا بین یک راس و یکی از اجدادش که در این صورت می‌شه پشتی و اگه به جز این سه تا باشه می‌شه یال عبوری.

[فاطمه رنجبر]

سلام اوکی متوجه شدم پس اول باید گراف روتبدیل به درخت کنیم بعدتشخیص بدیم یالها رو
ممممممممممممممممممممممنون

[L3ic]

نوع پیمایش درخت خیلی تاثیر گذاره تو انتخاب یال ها که معمولا تو سوال ذکر میشه که حتما دقت کنید
بقیه توضیحات رو دوست خوبمون دادند
موفق باشید

[happy07]

خواهش می‌کنم.
فقط یه سری نکات و قضایا باقی موندن، مثلا اینکه طوقه رو ما یال پشتی درنظر می‌گیریم.
در الگوریتم جستجوی عمق اول هر یال گراف، یا درختی است یا عقبی و.... که توی کتاب‌ها هستند....