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

پیمایش DFS و تشخیص نوع یال

ارسال:
  

Ametrine پرسیده:

پیمایش DFS و تشخیص نوع یال

سلام

یه سوال از کتاب مدرسان دارم.
این گراف جهت دار رو داده گفته از گره یک شروع میکنیم و پیمایش DFS رو مینویسیم.
یالهای forward (پیشرو) چندتاست؟


پیمایشی که من نوشتم درسته؟


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

۰
ارسال:
  

Densike پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

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

ارسال:
  

Ametrine پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

(۲۹ آبان ۱۳۹۳ ۱۰:۳۷ ق.ظ)Densike نوشته شده توسط:  سلام دوست عزیز .. همزمان با پیمایش DFS تمام گره ها و یال هایی که طی میکنی رو به صورت یک درخت جداگانه بکش .. تمام این یال هایی که تو درختی که کشیدی هستند یال درختی هستند
حالا این یال درختی ها رو گرافت بزار کنار ، یه سری یال دیگه هستند توی DFS استفاده نشدن ...
یه یال رو بردار ، توی درختی که کشیدی نگاه کن ببین کسی که یال ازش خارج شده جد کسی هست که یال بهش،وارد شده ؟ ... اگر بود یعنی یال forward هست
ممنون از توضیحاتتون

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

۰
ارسال:
  

Hamid_0311 پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل (صلیبی هم بهش میگن) به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
[تصویر:  317773_35180382792163118384.jpg]

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

ارسال:
  

Ametrine پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

(۲۹ آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط:  با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
ممنون از پاسختون.
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Densike پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

(۲۹ آبان ۱۳۹۳ ۱۱:۲۶ ق.ظ)Ametrine نوشته شده توسط:  
(29 آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط:  با سلام دوست عزیز این گراف یک یال پیشرو داره و یالی هست که از ۱ به ۸ میره
دقت کنید یال پیشرو یال غیر درختی هست که از جد به نسل میره
یال عقب رو یالی هست که در(u,v) راس u را به راس جدش v وصل می کنه و اصولا یال های که ایجاد حلقه می کنن عقب رو هستن
یال متقابل به سایر یال ها می گیم که می تونن مابین راس های درخت قرار بگیرند البته تا زمانی که یک راس جد راس دیگر نباشه
ممنون از پاسختون.
پس یک یال پیشرو داره ولی مدرسان نوشته که اصلاً پیشرو نداره.
اون دوتا آرایه هست. طبق الگوریتم DFS:
d زمان کشف گره discovery time
f زمان پایان بررسی گره finishing time

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

ارسال:
  

Ametrine پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

(۲۹ آبان ۱۳۹۳ ۱۱:۳۵ ق.ظ)Densike نوشته شده توسط:  من کلاس های مدرسان میرم دکتر ظهیری استاد مدرسان،اصلا از رو این کتاب درس نمیده غلط زیاد داره بعضی جاها،بهش استناد نکن
خیلی هم خوب!
کتابِ بدون اشتباه ‌م آرزوست! :دی

(۲۹ آبان ۱۳۹۳ ۱۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط:  اگر زیاد متوجه نمیشید تو بخش گراف های کتاب clrs بخونید توضیح خوبی داده البته فکر کنم توی کتاب دکتر قلی زاده هم توضیح داده باشه
CLRS از نظر من سخت توضیح داده.
کتاب دکتر قلی زاده کدومه؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Hamid_0311 پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

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

ارسال:
  

Densike پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

(۳۰ آبان ۱۳۹۳ ۰۱:۲۱ ق.ظ)Hamid_0311 نوشته شده توسط:  دوست عزیز کتاب قلی زاده کتاب زیاد خوبی نیست و من یه جزوه ازش دیده بودم
ولی clrs هم براتون سخته پوران بخونید خلاصه مطالب clrs هست البته بگم کتاب های مدرسان توی رشته کامپیوتر به جز امار و پایگاه داده اش من ندیدم کسی ازشون حرفی بزنه بهتره یکم تحقیق کنید و بخونیدشون موفق باشید.

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

۰
ارسال: #۱۰
  

Aurora پاسخ داده:

RE: پیمایش DFS و تشخیص نوع یال

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تشخیص گوگل مپس با Live View AR برای مکان دقیق elecomco ۱ ۴,۲۱۲ ۰۵ بهمن ۱۳۹۹ ۰۲:۴۹ ب.ظ
آخرین ارسال: kooshaideal1
  تشخیص خطا در تحلیلگر لغوی یا نحوی zahra2012 ۵ ۸,۲۲۸ ۲۶ مرداد ۱۳۹۷ ۰۴:۲۹ ب.ظ
آخرین ارسال: tohid.salmani
  تشخیص کاراکتر با شبکه عصبی safoora s ۴ ۴,۱۷۲ ۱۸ مرداد ۱۳۹۷ ۱۰:۵۰ ب.ظ
آخرین ارسال: kilookiloo
  تشخیص دو قضیه از هم Mr.R3ZA ۵ ۵,۴۵۷ ۳۱ اردیبهشت ۱۳۹۷ ۱۲:۱۴ ق.ظ
آخرین ارسال: pioneer01
  تشخیص گروه در شبکه های اجتماعی osho ۴۸ ۳۴,۲۸۳ ۲۸ فروردین ۱۳۹۷ ۰۷:۵۲ ب.ظ
آخرین ارسال: atahmasebi
  پیمایش پیشوندی درخت دودویی naghmeh70 ۲ ۳,۰۹۲ ۱۵ فروردین ۱۳۹۷ ۰۲:۲۹ ب.ظ
آخرین ارسال: naghmeh70
  نوع بیمه Ella ۰ ۱,۹۰۹ ۰۲ اسفند ۱۳۹۶ ۰۳:۳۳ ب.ظ
آخرین ارسال: Ella
Exclamation تشخیص نوع زبان و گرامر به صورت تستی و سریع kamran_maneshtir ۰ ۲,۲۴۶ ۰۲ بهمن ۱۳۹۶ ۰۷:۴۶ ب.ظ
آخرین ارسال: kamran_maneshtir
  تشخیص توالی پذیر نمایی (VSS) jumper ۰ ۱,۵۶۴ ۲۴ دى ۱۳۹۶ ۱۰:۱۹ ق.ظ
آخرین ارسال: jumper
  تشخیص بیت باارزش-مدارات ترتیبی Sepideh96 ۱ ۱,۸۰۲ ۳۰ آذر ۱۳۹۶ ۱۲:۵۶ ق.ظ
آخرین ارسال: msour44

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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