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

در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟

ارسال:
  

payman84ce پرسیده:

در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟

سلام در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟

۰
ارسال:
  

Aurora پاسخ داده:

RE: bfs=dfs

(۰۷ بهمن ۱۳۹۰ ۰۸:۰۶ ب.ظ)payman84ce نوشته شده توسط:  سلام در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟

سلام در صورتی این دو یکسانند که درخت حاصل از پیمایش آنها همان گراف اولیه باشد. یعنی گراف اولیه هیچ یال اضافه تری نسبت به درخت حاصل از پیمایش نداشته باشد و با پیمایش گراف دوباره به درخت اولیه برسیم. پس گراف باید دور نداشته باشد و لزوما هم هر گرافی که دور ندارد پیمایش BFS و DFS آن یکسان نیست.
[تصویر:  64845_1_1379095681.png]
مثلا در شکل اول با وجود نبودن دور ولی دو پیمایش یکسان نیستند ولی در دومی دو پیمایش یکسانند.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟ Masoud05 ۲ ۴,۲۹۰ ۲۰ دى ۱۳۹۱ ۰۸:۳۲ ب.ظ
آخرین ارسال: reza_d500
  مسئله مهم در پیمایش Masoud05 ۵ ۳,۲۷۱ ۰۸ آبان ۱۳۹۱ ۱۰:۵۹ ب.ظ
آخرین ارسال: esi
  تفاوت لیست مجاورت با ماتریس مجاورت گراف پشتکار ۲ ۳,۷۴۱ ۲۵ بهمن ۱۳۹۰ ۰۷:۰۸ ب.ظ
آخرین ارسال: پشتکار
  تشخیص شلوغ یا خلوت بودن گراف netsupport ۱ ۱,۴۰۳ ۰۵ بهمن ۱۳۹۰ ۰۱:۲۷ ق.ظ
آخرین ارسال: rad.bahar
  گراف همبند تست vijay ۹ ۳,۵۵۶ ۲۳ دى ۱۳۹۰ ۱۱:۰۳ ب.ظ
آخرین ارسال: sasanlive
  درجه ورودی راس در گراف homa ۷ ۱,۹۲۶ ۰۷ دى ۱۳۹۰ ۱۲:۴۱ ق.ظ
آخرین ارسال: pos
  حداکثر تعداد عناصر در سطح h هیپ ؟ sos006 ۲ ۱,۸۶۹ ۱۵ مرداد ۱۳۹۰ ۱۱:۱۶ ب.ظ
آخرین ارسال: hadi_m
  مرتبه زمانی پیمایش میان ترتیب bst؟ sos006 ۳ ۲,۵۹۹ ۲۹ دى ۱۳۸۹ ۰۴:۴۶ ب.ظ
آخرین ارسال: حامد
  جزوه خوب درمورد گراف‌؟ + سئوالی از DFS saria ۴ ۴,۴۳۸ ۲۱ دى ۱۳۸۹ ۱۰:۱۱ ب.ظ
آخرین ارسال: ۵۴m4n3h

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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