المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:زمان شروع و پایان گره‌ها در پیمایش میان‌ترتیب

زمان شروع و پایان گره‌ها در پیمایش میان‌ترتیب

تعریف

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

فرض کنید شمارنده‌ی C داشته باشیم که مقدار آن در ابتدا برابر یک باشد و با هر ورود و خروج از هر رأسی در طول پیمایش، یک واحد به مقدار آن افزوده شود.

زمان شروع یک رأس در پیمایش را مقدار C در زمان ورود به آن و زمان پایان رأس را مقدار C در زمان خروج از آن در نظر می‌گیریم.

الگوریتم

فرض کنید بر روی درخت T پیمایش عمق‌اول را اجرا نماییم. در این پیمایش بازگشتی در زمان ورود به رأس x مقدار $s[x[$ را برابر C و در حین پایان کار الگوریتم بر روی رأس x، مقدار $f[x]$ را برابر با C قرار می‌دهیم.

به مقادیر $s[x], f[x]$ به ترتیب زمان شروع و زمان پایان رأس x می‌گوییم.

کابردها

مثال: صورت مسئله اینجا می‌آید.

پاسخ

پاسخ مسئله اینجا می‌آید

پیچیدگی‌ الگوریتم

پیاده‌سازی اولیه

A.c
#include <iostream>
int main() {
}

پیاده‌سازی سریع‌تر

‌‌B.c
#include <iostream>
int main() {
}

مسائل نمونه

مراجع


ابزار صفحه