اُپدیا

درخت جست‌و‌جوی عمق‌اول در واقع یک درخت ریشه‌دار است که ریشه آن همان رأسی است که جست‌و‌جو از آن آغاز شده است. این درخت شامل تمام یال‌هایی است که در پیمایش عمق‌اول طی شده‌اند و پدر هر راس، راسی است که در پیمایش از آن وارد این راس شده‌ایم. پس واضح است که برخی از یال‌ها در درخت نمی‌آیند و همچنین این درخت ریشه‌دار دور ندارد چون هر رأسی تنها یک پدر دارد! به طور کلی یال‌های گراف اصلی را میتوان به ۴ دسته تقسیم کرد:

1. یال‌‌های درخت ساخته شده (یال درختی یا Tree Edge)
2. از یک راس به جدش (یال عقب‌رو یا Back Edge)
3. از یک راس به زیر درختش (یال جلو‌رو یا Forward Edge)
4. هیچ کدام از سه مورد بالا (یال میانی یا Corss Edge)

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

همچنین در گراف‌های جهت‌دار یال میانی از سمت چپ درخت به سمت راست نداریم. (یعنی اگر یال میانی از $v$ به $u$ داشته باشیم حتما زمان خاتمه $u$ زودتر از $v$ است)