زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۶:۲۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

انواع یال ها

ارسال:
  

iCanDoIt پرسیده:

انواع یال ها

سلام و درود.
دوستان هم توی کتاب ساختمان داده و هم توی کتاب الگوریتم پوران پژوهش اومده یال درختی، یا جلو رو، یال پشتی، یال عبوری رو توضیح داده و اصلا معلوم نیست چی گفته اگه میشه محبت کنید با یه مثال همشون رو توضیح بدید.

با تشکر
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

neghab01 پاسخ داده:

RE: انواع یال ها

سلام.
با فرضِ پیمایش 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 جنگل را بدست می آوردید.
۲/سپس یال های غیر درختی را رسم کنید(ترجیحا با رنگ دیگر یا نقطه چین) و شرایط بالا رو در اونها جستجو کنید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  هاست یا میزبانی وب چیست؛ انواع آن کدامند؟ B0020 ۰ ۸۰۸ ۰۹ فروردین ۱۴۰۲ ۰۲:۵۷ ب.ظ
آخرین ارسال: B0020
  فروش انواع دستگیره دیجیتال و هوشمند آریالاک arialock ۰ ۱,۱۱۳ ۲۶ تیر ۱۴۰۱ ۰۳:۲۹ ب.ظ
آخرین ارسال: arialock
  دانلود رایگان تعمیر انواع مادربردهای PC و Server SamanehRashvand ۰ ۱,۹۹۷ ۲۶ مهر ۱۳۹۸ ۰۲:۲۴ ق.ظ
آخرین ارسال: SamanehRashvand
  سایت های انواع دیتاست (عادی - حجیم و ... ) fo-eng ۲۳ ۱۸,۹۲۱ ۲۲ مرداد ۱۳۹۸ ۱۱:۰۸ ب.ظ
آخرین ارسال: fo-eng
  مفهوم انواع آنتروپی و ویژگی های غیر خطی سیگنال مغز baharkhanoom ۰ ۱,۹۸۱ ۲۶ خرداد ۱۳۹۷ ۱۰:۲۷ ب.ظ
آخرین ارسال: baharkhanoom
  تعمیرات تخصصی انواع اسکرابر های دستی و سرنشین دار aradnovin ۰ ۳ ۰۴ آذر ۱۳۹۶ ۱۲:۰۴ ب.ظ
آخرین ارسال: aradnovin
  انواع شرکت های سهامی comreg ۰ ۱,۶۲۹ ۲۳ شهریور ۱۳۹۶ ۱۲:۴۸ ب.ظ
آخرین ارسال: comreg
  معرفی منابع و گرایش های مرتبط با فایل های صوتی و تصویری و پخش کننده های صوت و تصویر R.g- ۴ ۴,۰۹۴ ۱۵ شهریور ۱۳۹۶ ۰۹:۳۲ ب.ظ
آخرین ارسال: blackhalo1989
Lightbulb انواع فرهنگ لغات در ترجمه متون انگلیسی asad.victory ۰ ۲,۶۰۷ ۰۷ تیر ۱۳۹۶ ۱۲:۵۴ ب.ظ
آخرین ارسال: asad.victory
  مسیر ساده با کمترین تعداد یال - IT 86 delete4all ۴ ۲,۳۵۷ ۲۳ اسفند ۱۳۹۵ ۰۸:۳۰ ق.ظ
آخرین ارسال: delete4all

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close