در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده، اگه میتونید لطف کنید این موضوع رو تشریح کنید.
مسعود جان کافیه یه نگاه کوچولو به فصل ۲۲ کتاب CLRS بندازی . من چون حفظش نکردم نمی تونم توضیح بدم . ولی خیلی ساده اس.
سوالای چند سال اخیر به طرز ناشیانه و ناجوانمردانه ای کپی تمرینات این کتابه .
دوست عزیز شما تو پیمایش bfs و dfs یه ترتیبی رو تو ملاقات نودها دارین. همون ترتیب رو می نویسین به عنوان d یعنی این یال رو ملاقات کردین. اما در مورد f تو پیمایش dfs یا bfs گاهی به نقطه ای می رسین که یا باید برگردین به نود قبلی یا دیگه راهی برای پیشروی ندارین. تو این موقعیت کنار d، زمان f رو می نویسین که این f هم همون ترتیب ملاقاته.
خیلی مفهوم ساده ایه. اگر نتونستم خوب تشریح کنم ببخش. می تونی به کتاب طراحی الگوریتم یوسفی پوران یا همون CLRS یه نگاهی بندازی.
(۱۰ بهمن ۱۳۸۹ ۱۱:۳۴ ب.ظ)Masoud05 نوشته شده توسط: در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده، اگه میتونید لطف کنید این موضوع رو تشریح کنید.۱ سال گذشت!
(۲۷ بهمن ۱۳۹۰ ۱۲:۰۱ ق.ظ)Masoud05 نوشته شده توسط:(10 بهمن ۱۳۸۹ ۱۱:۳۴ ب.ظ)Masoud05 نوشته شده توسط: در پیمایش گراف بصورت dfs و bfs می توان به گره‌ها بر اساس اولین و آخرین زمان مشاهده مقدار داد که توی سال های اخیر چندتا تست ازش اومده، اگه میتونید لطف کنید این موضوع رو تشریح کنید.۱ سال گذشت!
کسی یه جواب خوب واسه این نداره؟؟؟ خواهشا سطح پایین توضبح بدید
الگوریتم dfs :
از گره مبدا شروع کنید ، به ترتیب که جلو میرید زمان ملاقات گره رو تویه d[v] ثبت کنید، اولین گره ۱ و گره بعدی ۲ و ...، هر جایی که دیگه راه جلو رو نداشتید و باید برگردید زمان آخرین ملاقات گره رو تو f[v] ثبت کنید. به همین ترتیب تا آخرین گره اینکار رو انجام بدید.
بر اساس این زمان ها می تونید نوع یال هارو مشخص کنید و تویه الگوریتم های مختلف ازش استفاده کنید مثلا یال درختی دارای خصوصیت زیره :
(یال از u به v ، گراف جهت دار ) d[u]<d[v]<f[v]<f[u] ، بقیه طبقه بندی یال هارو هم می تونید تو clrs ببینید که خیلی راحته.
تویه گراف های بدون جهت هم طبقه یال ها مشخصه و تویه یکی از تمرین های clrs گفته شده.
الگوریتم bfs : مشابه الکوریتم dfs زمان ها رو ثبت می کنیم و طبقه بندی یال هاشم تو clrs گفته چطوری، هم برای گراف جهت دار و هم بدون جهت.
تو بیشتر مسائل هم از زمان های ثبت شده برای پیمایش dfs استفاده میشه (مثل SCC، مرتب سازی توپولوژیک و ...) به همین علت درک پیمایش عمقی خیلی مهمه و هم کاربرد زیاد داره و هم تستهای زیادی ازش میاد تو کنکور .