تالار گفتمان مانشت

سلام

یه سوال از کتاب مدرسان دارم.
این گراف جهت دار رو داده گفته از گره یک شروع میکنیم و پیمایش DFS رو مینویسیم.
یالهای forward (پیشرو) چندتاست؟
[attachment=17269]
پیمایشی که من نوشتم درسته؟
[attachment=17270]
حالا برای تشخیص یال پیشرو طبق تعریف اگه یک یال (u,v) داشته باشیم اگه u.d<v.d<v.f<u.f بشه اونوقت یال (u,v) درختی یا پیشرو هست.
من نمیتونم از رو این تعریف یال ها رو پیدا کنم!
چطوری درختی و پیشرو رو از هم تشخیص بدم؟
یعنی اگه یال پیشرو تو گراف باشه و همون یال تو پیمایش درختی باشه، درختی حساب میشه؟! اگه اینجوری باشه اونوقت پیشرو کدومه؟!
لطفاً راهنمایی کنید.

سلام دوست عزیز .. همزمان با پیمایش DFS تمام گره ها و یال هایی که طی میکنی رو به صورت یک درخت جداگانه بکش .. تمام این یال هایی که تو درختی که کشیدی هستند یال درختی هستند
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست

(29 آبان 1393 10:37 ق.ظ)Densike نوشته شده توسط: [ -> ]سلام دوست عزیز .. همزمان با پیمایش DFS تمام گره ها و یال هایی که طی میکنی رو به صورت یک درخت جداگانه بکش .. تمام این یال هایی که تو درختی که کشیدی هستند یال درختی هستند
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست

ممنون از توضیحاتتون

اگه درست متوجه شده باشم.
برای تشخیص یال forward :
باید یالهایی که توی پیمایش درختی هستن رو کلاً کاری نداشته باشم.
اونایی که توی گراف هستن ولی تو درخت نیستن رو یکی یکی امتحان کنم.
مثلاً الان یال(8و1) که تو گراف هست توی درخت نگا میکنم میبینیم که گره 1 جد گره 8 هست ( یال از 1 خارج شده و به 8 وارد شده.)
پس الان میشه گفت اینجا یک یال forward داریم.
مدرسان نوشته که اصلاً یال forward نداره!
ممکنه پیمایشی که نوشتم رو چک کنید؟
چون زمان های d و f که بدست میارم با حل مدرسان یکی نمیشه!

با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از 1 به 8 میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل (صلیبی هم بهش میگن) به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه


اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشه

(29 آبان 1393 11:21 ق.ظ)Hamid_0311 نوشته شده توسط: [ -> ]با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه

ممنون از پاسختون.
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time

(29 آبان 1393 11:26 ق.ظ)Ametrine نوشته شده توسط: [ -> ]

(29 آبان 1393 11:21 ق.ظ)Hamid_0311 نوشته شده توسط: [ -> ]با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه

ممنون از پاسختون.
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time

من کلاس های مدرسان میرم دکتر ظهیری استاد مدرسان،اصلا از رو این کتاب درس نمیده غلط زیاد داره بعضی جاها،بهش استناد نکن

(29 آبان 1393 11:35 ق.ظ)Densike نوشته شده توسط: [ -> ]من کلاس های مدرسان میرم دکتر ظهیری استاد مدرسان،اصلا از رو این کتاب درس نمیده غلط زیاد داره بعضی جاها،بهش استناد نکن

خیلی هم خوب!
کتابِ بدون اشتباه ‌م آرزوست! :دی

(29 آبان 1393 11:21 ق.ظ)Hamid_0311 نوشته شده توسط: [ -> ]اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشه

CLRS از نظر من سخت توضیح داده.
کتاب دکتر قلی زاده کدومه؟

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

(30 آبان 1393 01:21 ق.ظ)Hamid_0311 نوشته شده توسط: [ -> ]دوست عزیز کتاب قلی زاده کتاب زیاد خوبی نیست و من یه جزوه ازش دیده بودم
ولی clrs هم براتون سخته پوران بخونید خلاصه مطالب clrs هست البته بگم کتاب های مدرسان توی رشته کامپیوتر به جز امار و پایگاه داده اش من ندیدم کسی ازشون حرفی بزنه بهتره یکم تحقیق کنید و بخونیدشون موفق باشید.

کتاب طراحی الگوریتم مدرسان رو جا انداختید ..بهترین کتاب الگوریتمه با اختلاف

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