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

مسئله مهم در پیمایش

ارسال:
  

Masoud05 پرسیده:

مسئله مهم در پیمایش

در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده‌، اگه میتونید لطف کنید این موضوع رو تشریح کنید.

۰
ارسال:
  

esi پاسخ داده:

مسئله مهم در پیمایش

الگوریتم dfs :
از گره مبدا شروع کنید ، به ترتیب که جلو میرید زمان ملاقات گره رو تویه d[v] ثبت کنید، اولین گره ۱ و گره بعدی ۲ و ...، هر جایی که دیگه راه جلو رو نداشتید و باید برگردید زمان آخرین ملاقات گره رو تو f[v] ثبت کنید. به همین ترتیب تا آخرین گره اینکار رو انجام بدید.

بر اساس این زمان ها می تونید نوع یال هارو مشخص کنید و تویه الگوریتم های مختلف ازش استفاده کنید مثلا یال درختی دارای خصوصیت زیره :
(یال از u به v ، گراف جهت دار ) d[u]<d[v]<f[v]<f[u] ، بقیه طبقه بندی یال هارو هم می تونید تو clrs ببینید که خیلی راحته.
تویه گراف های بدون جهت هم طبقه یال ها مشخصه و تویه یکی از تمرین های clrs گفته شده.
الگوریتم bfs : مشابه الکوریتم dfs زمان ها رو ثبت می کنیم و طبقه بندی یال هاشم تو clrs گفته چطوری، هم برای گراف جهت دار و هم بدون جهت.
تو بیشتر مسائل هم از زمان های ثبت شده برای پیمایش dfs استفاده میشه (مثل SCC، مرتب سازی توپولوژیک و ...) به همین علت درک پیمایش عمقی خیلی مهمه و هم کاربرد زیاد داره و هم تستهای زیادی ازش میاد تو کنکور .

۰
ارسال:
  

parsaNA پاسخ داده:

مسئله مهم در پیمایش

مسعود جان کافیه یه نگاه کوچولو به فصل ۲۲ کتاب CLRS بندازی . من چون حفظش نکردم نمی تونم توضیح بدم . ولی خیلی ساده اس.

سوالای چند سال اخیر به طرز ناشیانه و ناجوانمردانه ای کپی تمرینات این کتابه .

۰
ارسال:
  

arshad90 پاسخ داده:

مسئله مهم در پیمایش

دوست عزیز شما تو پیمایش bfs و dfs یه ترتیبی رو تو ملاقات نودها دارین. همون ترتیب رو می نویسین به عنوان d یعنی این یال رو ملاقات کردین. اما در مورد f تو پیمایش dfs یا bfs گاهی به نقطه ای می رسین که یا باید برگردین به نود قبلی یا دیگه راهی برای پیشروی ندارین. تو این موقعیت کنار d، زمان f رو می نویسین که این f هم همون ترتیب ملاقاته.

خیلی مفهوم ساده ایه. اگر نتونستم خوب تشریح کنم ببخش. می تونی به کتاب طراحی الگوریتم یوسفی پوران یا همون CLRS یه نگاهی بندازی.

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: مسئله مهم در پیمایش

(۱۰ بهمن ۱۳۸۹ ۱۱:۳۴ ب.ظ)Masoud05 نوشته شده توسط:  در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده‌، اگه میتونید لطف کنید این موضوع رو تشریح کنید.
۱ سال گذشت!

ارسال:
  

anita_66 پاسخ داده:

RE: مسئله مهم در پیمایش

(۲۷ بهمن ۱۳۹۰ ۱۲:۰۱ ق.ظ)Masoud05 نوشته شده توسط:  
(10 بهمن ۱۳۸۹ ۱۱:۳۴ ب.ظ)Masoud05 نوشته شده توسط:  در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده‌، اگه میتونید لطف کنید این موضوع رو تشریح کنید.
۱ سال گذشت!

کسی یه جواب خوب واسه این نداره؟؟؟ خواهشا سطح پایین توضبح بدید
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۸۷۸ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  تصمیم گیری مهم درباره مکان سرور سایت admin ۴ ۴,۹۲۳ ۲۸ دى ۱۴۰۰ ۰۳:۵۹ ب.ظ
آخرین ارسال: mahsa3323
  کمک به حل مسئله Moha33 ۰ ۱,۳۳۶ ۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ
آخرین ارسال: Moha33
  سوال مهم از کمتازیا jamshid51 ۰ ۲,۰۱۵ ۲۹ مهر ۱۳۹۹ ۱۰:۰۷ ب.ظ
آخرین ارسال: jamshid51
Shocked کامپیوتر یا هنر، مسئله این است arian_61 ۲ ۴,۶۶۹ ۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ
آخرین ارسال: packationmachinery
  مسئله n_وزیر Sanazzz ۲ ۳,۳۸۷ ۱۱ بهمن ۱۳۹۷ ۰۳:۰۳ ب.ظ
آخرین ارسال: Sanazzz
  ۱۴۷ ای تی ___انتخاب رشته مهم مهم _خواهشا کمکم کنید وقت ندارم Rezaprince ۱ ۲,۵۱۸ ۱۲ مرداد ۱۳۹۷ ۰۶:۱۷ ب.ظ
آخرین ارسال: Happiness.72
  توصیه های مهم در رابطه با انتخاب رشته (مهم) Happiness.72 ۰ ۲,۱۸۰ ۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ
آخرین ارسال: Happiness.72
  سوال مهم و فوری در مورد انتخاب رشته siiib70 ۲ ۴,۳۳۰ ۰۸ اردیبهشت ۱۳۹۷ ۰۵:۳۴ ب.ظ
آخرین ارسال: siiib70
  پیمایش پیشوندی درخت دودویی naghmeh70 ۲ ۳,۱۴۵ ۱۵ فروردین ۱۳۹۷ ۰۲:۲۹ ب.ظ
آخرین ارسال: naghmeh70

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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