با سلام و خسته نباشید خدمت دوستان محترم
در پیمایش 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]](https://img.manesht.ir/406355_qeie0spyne6qi6vfelmj.png)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۶ خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط: با سلام و خسته نباشید خدمت دوستان محترمدر فایل ضمیمه شده یال‌های مختلف با رنگ و pattern متفاوت نشون داده شده‌اند.
در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟
ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .
با تشکر
در پیماش درخت DFS، هر یال [tex](u,v)[/tex] که پیمایش شده باشه، یال عبوری هست: Tree Edge
اگر رأس u نیای رأس v باشد ولی این یال پیمایش نشده باشد، یال فوروارد یا پیشرو هست
یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست (همانطور که در شکل، a نیای e هست در درخت ولی از e به a یالی وجود داره در گراف).
بقیه‌ی یال‌ها cross یا نقاطعی هستند.
[attachment=20012]
(۱۶ خرداد ۱۳۹۵ ۰۶:۲۶ ب.ظ)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 به دست اومده :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از جوابتون.
در یال بازگشتی نباید u پدر v باشه؟؟
(۱۶ خرداد ۱۳۹۵ ۰۷:۴۹ ب.ظ)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 به دست اومده :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از جوابتون.
در یال بازگشتی نباید u پدر v باشه؟؟
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت
(۱۶ خرداد ۱۳۹۵ ۰۸:۱۰ ب.ظ)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 به دست اومده :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از جوابتون.
در یال بازگشتی نباید u پدر v باشه؟؟
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت
۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
(۱۶ خرداد ۱۳۹۵ ۰۹:۱۹ ب.ظ)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 به دست اومده :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از جوابتون.
در یال بازگشتی نباید u پدر v باشه؟؟
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت
۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
عذر خواهی میکنم.گویا جابه جا نوشتم.الان صحیح میکنم.
تکس که مینویسم همیشه گیجم میکنه.اصلاح شد.فقط یه جابه جایی بود.همه ی تعاریف و مثال ها درستن
(۱۶ خرداد ۱۳۹۵ ۰۹:۲۴ ب.ظ)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 به دست اومده :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنون از جوابتون.
در یال بازگشتی نباید u پدر v باشه؟؟
من الان یه رنگ بندی میکنم از پاسخم،بعد دوباره بخونش با دقت.
از مثال کاربر behnam5670 هم استفاده کن.از توضیحات من و مثال ایشون. لطفا با دقت
۱/یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست.
۲/یال هایی مانند (u,v) که در جنگل پوشای DFS استفاده نشده اند و راس v یک والد برای u میباشد.
این دو تعریف با هم فرق داره !
تو مثال خودتون یال v5 به v2 بازگشتیه یا پیشرو؟؟
عذر خواهی میکنم.گویا جابه جا نوشتم.الان صحیح میکنم.
اصلاح شد.فقط یه جابه جایی بود.همه ی تعاریف و مثال ها درستن
خواهش میکنم
ممنون که وقت گذاشتین خیلی لطف کردین
(۱۶ خرداد ۱۳۹۵ ۰۶:۴۰ ب.ظ)behnam5670 نوشته شده توسط:(16 خرداد ۱۳۹۵ ۰۶:۱۲ ب.ظ)hamidrm509 نوشته شده توسط: با سلام و خسته نباشید خدمت دوستان محترمدر فایل ضمیمه شده یال‌های مختلف با رنگ و pattern متفاوت نشون داده شده‌اند.
در پیمایش dfs یال های عبوری ، یال های پیشرو ، یال های بازگشتی و یال های درختی کدوما هستن ؟؟
ممنون میشم اگه با مثال جوابمو بدین که خوب متوجه بشم . خیلی مهمه برام .
با تشکر
در پیماش درخت DFS، هر یال [tex](u,v)[/tex] که پیمایش شده باشه، یال عبوری هست: Tree Edge
اگر رأس u نیای رأس v باشد ولی این یال پیمایش نشده باشد، یال فوروارد یا پیشرو هست
یال بازگشتی یال‌هایی هستند که v رو به u به صورت بازگشتی (عقبگرد) متصل می‌کنند. یعنی در درخت، u نیای v هست (همانطور که در شکل، a نیای e هست در درخت ولی از e به a یالی وجود داره در گراف).
بقیه‌ی یال‌ها cross یا نقاطعی هستند.
خیلی ممنون از جوابتون ..خیلی کمک کرد.