۰
subtitle
ارسال: #۱
  
پیمایش DFS و تشخیص نوع یال
سلام
یه سوال از کتاب مدرسان دارم.
این گراف جهت دار رو داده گفته از گره یک شروع میکنیم و پیمایش DFS رو مینویسیم.
یالهای forward (پیشرو) چندتاست؟
پیمایشی که من نوشتم درسته؟
حالا برای تشخیص یال پیشرو طبق تعریف اگه یک یال (u,v) داشته باشیم اگه u.d<v.d<v.f<u.f بشه اونوقت یال (u,v) درختی یا پیشرو هست.
من نمیتونم از رو این تعریف یال ها رو پیدا کنم!
چطوری درختی و پیشرو رو از هم تشخیص بدم؟
یعنی اگه یال پیشرو تو گراف باشه و همون یال تو پیمایش درختی باشه، درختی حساب میشه؟! اگه اینجوری باشه اونوقت پیشرو کدومه؟!
لطفاً راهنمایی کنید.
یه سوال از کتاب مدرسان دارم.
این گراف جهت دار رو داده گفته از گره یک شروع میکنیم و پیمایش DFS رو مینویسیم.
یالهای forward (پیشرو) چندتاست؟
پیمایشی که من نوشتم درسته؟
حالا برای تشخیص یال پیشرو طبق تعریف اگه یک یال (u,v) داشته باشیم اگه u.d<v.d<v.f<u.f بشه اونوقت یال (u,v) درختی یا پیشرو هست.
من نمیتونم از رو این تعریف یال ها رو پیدا کنم!
چطوری درختی و پیشرو رو از هم تشخیص بدم؟
یعنی اگه یال پیشرو تو گراف باشه و همون یال تو پیمایش درختی باشه، درختی حساب میشه؟! اگه اینجوری باشه اونوقت پیشرو کدومه؟!
لطفاً راهنمایی کنید.
۰
ارسال: #۲
  
RE: پیمایش DFS و تشخیص نوع یال
سلام دوست عزیز .. همزمان با پیمایش DFS تمام گره ها و یال هایی که طی میکنی رو به صورت یک درخت جداگانه بکش .. تمام این یال هایی که تو درختی که کشیدی هستند یال درختی هستند
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست
ارسال: #۳
  
RE: پیمایش DFS و تشخیص نوع یال
(۲۹ آبان ۱۳۹۳ ۱۰:۳۷ ق.ظ)Densike نوشته شده توسط: سلام دوست عزیز .. همزمان با پیمایش DFS تمام گره ها و یال هایی که طی میکنی رو به صورت یک درخت جداگانه بکش .. تمام این یال هایی که تو درختی که کشیدی هستند یال درختی هستندممنون از توضیحاتتون
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست
اگه درست متوجه شده باشم.
برای تشخیص یال forward :
باید یالهایی که توی پیمایش درختی هستن رو کلاً کاری نداشته باشم.
اونایی که توی گراف هستن ولی تو درخت نیستن رو یکی یکی امتحان کنم.
مثلاً الان یال(۸و۱) که تو گراف هست توی درخت نگا میکنم میبینیم که گره ۱ جد گره ۸ هست ( یال از ۱ خارج شده و به ۸ وارد شده.)
پس الان میشه گفت اینجا یک یال forward داریم.
مدرسان نوشته که اصلاً یال forward نداره!
ممکنه پیمایشی که نوشتم رو چک کنید؟
چون زمان های d و f که بدست میارم با حل مدرسان یکی نمیشه!
۰
ارسال: #۴
  
RE: پیمایش DFS و تشخیص نوع یال
با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل (صلیبی هم بهش میگن) به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشه
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل (صلیبی هم بهش میگن) به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشه
ارسال: #۵
  
RE: پیمایش DFS و تشخیص نوع یال
(۲۹ آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط: با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میرهممنون از پاسختون.
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time
ارسال: #۶
  
RE: پیمایش DFS و تشخیص نوع یال
(۲۹ آبان ۱۳۹۳ ۱۱:۲۶ ق.ظ)Ametrine نوشته شده توسط:(29 آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط: با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میرهممنون از پاسختون.
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time
من کلاس های مدرسان میرم دکتر ظهیری استاد مدرسان،اصلا از رو این کتاب درس نمیده غلط زیاد داره بعضی جاها،بهش استناد نکن
ارسال: #۷
  
RE: پیمایش DFS و تشخیص نوع یال
(۲۹ آبان ۱۳۹۳ ۱۱:۳۵ ق.ظ)Densike نوشته شده توسط: من کلاس های مدرسان میرم دکتر ظهیری استاد مدرسان،اصلا از رو این کتاب درس نمیده غلط زیاد داره بعضی جاها،بهش استناد نکنخیلی هم خوب!
کتابِ بدون اشتباه م آرزوست! :دی
(۲۹ آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط: اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشهCLRS از نظر من سخت توضیح داده.
کتاب دکتر قلی زاده کدومه؟
۰
ارسال: #۸
  
RE: پیمایش DFS و تشخیص نوع یال
دوست عزیز کتاب قلی زاده کتاب زیاد خوبی نیست و من یه جزوه ازش دیده بودم
ولی clrs هم براتون سخته پوران بخونید خلاصه مطالب clrs هست البته بگم کتاب های مدرسان توی رشته کامپیوتر به جز امار و پایگاه داده اش من ندیدم کسی ازشون حرفی بزنه بهتره یکم تحقیق کنید و بخونیدشون موفق باشید.
ولی clrs هم براتون سخته پوران بخونید خلاصه مطالب clrs هست البته بگم کتاب های مدرسان توی رشته کامپیوتر به جز امار و پایگاه داده اش من ندیدم کسی ازشون حرفی بزنه بهتره یکم تحقیق کنید و بخونیدشون موفق باشید.
ارسال: #۹
  
RE: پیمایش DFS و تشخیص نوع یال
(۳۰ آبان ۱۳۹۳ ۰۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط: دوست عزیز کتاب قلی زاده کتاب زیاد خوبی نیست و من یه جزوه ازش دیده بودم
ولی clrs هم براتون سخته پوران بخونید خلاصه مطالب clrs هست البته بگم کتاب های مدرسان توی رشته کامپیوتر به جز امار و پایگاه داده اش من ندیدم کسی ازشون حرفی بزنه بهتره یکم تحقیق کنید و بخونیدشون موفق باشید.
کتاب طراحی الگوریتم مدرسان رو جا انداختید ..بهترین کتاب الگوریتمه با اختلاف
۰
ارسال: #۱۰
  
RE: پیمایش DFS و تشخیص نوع یال
درباره منابع اینجا صحبت نکنید.
فقط جواب سوال اینجا بحث بشه.
فقط جواب سوال اینجا بحث بشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close