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

انواع یال ها در پیمایش dfs

ارسال:
  

hamidrm509 پرسیده:

Information انواع یال ها در پیمایش dfs

با سلام و خسته نباشید خدمت دوستان محترم

در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟

ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .

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

۰
ارسال:
  

Saman پاسخ داده:

Wink RE: انواع یال ها در پیمایش dfs

سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.

[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

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

ارسال:
  

hamidrm509 پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Saman پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟
اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقتBlush
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

hamidrm509 پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟
اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقتBlush

۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Saman پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۹:۱۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟
اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقتBlush

۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
پیشرو هست.
عذر خواهی میکنم.گویا جابه جا نوشتم.الان صحیح میکنم.Smile تکس که مینویسم همیشه گیجم میکنه.

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

ارسال:
  

hamidrm509 پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۹:۲۴ ب.ظ)samanbeigmiri نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۹:۱۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)samanbeigmiri نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)hamidrm509 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)samanbeigmiri نوشته شده توسط:  سلام

یال های درختی :یال هایی که در پیمایش DFS هستند یال های درختی بهش میگن.(یال های درختی در پیمایش DFS به صورت خط ممتد نشان داده شده اند)
یال پشتی(بازگشتی) : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
[tex](V1,V4)\: ,\: (V2,V5)[/tex]

یال های پیشرو : یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس u یک والد برای v میباشد.
[tex](V4,V2)\: ,\: (V5,V1)[/tex]

یال عبوری(تقاطعی) : یالی که هیچ کدوم از موارد بالا نیست.یعنی در درخت DFS هیچ کدام والد دیگری نیست
[tex](V7,V2)[/tex]
شکل اول گراف و شکل دوم پیمایش درختی به همراه یال هاست که از اجرای DFS به دست اومده :

[تصویر:  406355_qeie0spyne6qi6vfelmj.png]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنون از جوابتون.

در یال بازگشتی نباید u پدر v باشه؟؟
اینی که میگید میشه پیشرو.
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقتBlush

۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
پیشرو هست.
عذر خواهی میکنم.گویا جابه جا نوشتم.الان صحیح میکنم.Smile تکس که مینویسم همیشه گیجم میکنه.

اصلاح شد.فقط یه جابه جایی بود.همه ی تعاریف و مثال ها درستن

خواهش میکنم Smile
ممنون که وقت گذاشتین خیلی لطف کردین

(۱۶ خرداد ۱۳۹۵ ۰۶:۴۰ ب.ظ)behnam5670 نوشته شده توسط:  
(16 خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط:  با سلام و خسته نباشید خدمت دوستان محترم

در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟

ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .

با تشکر
در فایل ضمیمه شده یال‌های مختلف با رنگ و pattern متفاوت نشون داده شده‌اند.
در پیماش درخت DFS، هر یال [tex](u,v)[/tex] که پیمایش شده باشه، یال عبوری هست: Tree Edge
اگر رأس u نیای رأس v باشد ولی این یال پیمایش نشده باشد، یال فوروارد یا پیشرو هست
یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست (همانطور که در شکل، a نیای e هست در درخت ولی از e به a یالی وجود داره در گراف).
بقیه‌ی یال‌ها cross یا نقاطعی هستند.


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

۱
ارسال:
  

Behnam‌ پاسخ داده:

RE: انواع یال ها در پیمایش dfs

(۱۶ خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط:  با سلام و خسته نباشید خدمت دوستان محترم

در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟

ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .

با تشکر
در فایل ضمیمه شده یال‌های مختلف با رنگ و pattern متفاوت نشون داده شده‌اند.
در پیماش درخت DFS، هر یال [tex](u,v)[/tex] که پیمایش شده باشه، یال عبوری هست: Tree Edge
اگر رأس u نیای رأس v باشد ولی این یال پیمایش نشده باشد، یال فوروارد یا پیشرو هست
یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست (همانطور که در شکل، a نیای e هست در درخت ولی از e به a یالی وجود داره در گراف).
بقیه‌ی یال‌ها cross یا نقاطعی هستند.


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



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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