سلام و درود.
دوستان هم توی کتاب ساختمان داده و هم توی کتاب الگوریتم پوران پژوهش اومده یال درختی، یا جلو رو، یال پشتی، یال عبوری رو توضیح داده و اصلا معلوم نیست چی گفته اگه میشه محبت کنید با یه مثال همشون رو توضیح بدید.
با تشکر
سلام.
با فرضِ پیمایش DFS من اینا رو توضیح میدم ://///قابل ذکر است یافتن این یال ها با پیمایش BFS هم امکان پذیر است
اولا برای این کار باید روی یک گراف پیمایش DFS رو بلد باشید :
یال درختی : یال هایی مانند (u,v) که در جنگل(دقت کن) پوشای DFS وجود دارند و برای پیمایش DFS استفاده شده اند.
(تا اینجا شما جنگل DFS رو با پیمایش به روشِ DFS به دست آوردید)
یال های عقب رونده یا پشتی : یال هایی مانند (u,v) که در جنگل پوشا استفاده نشده اند و راس V یک
جد یا والد برای U باشد{ اینجا دقت کن که وقتی میگه جد، منظورش اینه که اگر دو راس رو مثال زد که در یک مسیر بودند باز هم میتونند این شرایط رو داشته باشند}/
مثلا : راسی مانند (v2,v5) که مثلا در این مسیر باشند :
v2v3v6v7v5
حالا باز هم اگر v5 یک جد یا والد باشد برای v2 این حالت درسته و میشه یال عقب رونده یا پشتی.(یعنی با حرکت از v5 بشود به v2 رسید،که v5 میشود جدِ v2 )
یال های پیش رو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس U یک جد یا والد برای V میباشد.مثالش میشه برعکس حالت بالا.
یال های تقاطعی : یال هایی مانند (u,v) که در جنگل استفاده نشده اند و راس u , v هیچ کدام جد یا والد دیگری نیست.
=====
برای حلِ مثال :
۱/ابتدا از پیمایش DFS جنگل را بدست می آوردید.
۲/سپس یال های غیر درختی را رسم کنید(ترجیحا با رنگ دیگر یا نقطه چین) و شرایط بالا رو در اونها جستجو کنید.