View Full Version : راهنمایی در مرود الگوریتم جستجوی عمق اول
NIMA_1981
چهارشنبه 01 آذر 1391, 16:26 عصر
سلام دوستان کسی الگوریتم dfs را بصورت غیر بازگستی میتونه بنویسه یا راهنمایی کنه که چطوری نوشته میشه
با تشکر
مسعود اقدسی فام
چهارشنبه 01 آذر 1391, 17:53 عصر
یه صف تعریف میکنید. هر عنصری رو که چاپ میکنید فرزندانش رو به ترتیب وارد صف میکنید. بعد اولین عنصر صف رو بر میدارید و همین کار رو تکرار میکنید. این عملیات تا زمانی انجام میشه که صف خالی بشه.
NIMA_1981
چهارشنبه 01 آذر 1391, 23:07 عصر
ممنون از راهنمایی خوب فرزندان رو چطوری وارد صف کنم بعد ممکنه خود اون فرزند بازم بچه داشته باشه میشه بیشتر راهنمایی کنید یا یک مثال بنویسید
با تشکر
مسعود اقدسی فام
چهارشنبه 01 آذر 1391, 23:58 عصر
ممنون از راهنمایی خوب فرزندان رو چطوری وارد صف کنم بعد ممکنه خود اون فرزند بازم بچه داشته باشه میشه بیشتر راهنمایی کنید یا یک مثال بنویسید
با تشکر
فرض کنید:
95387
وقتی گره یک خونده میشه گره دو و سه وارد صف میشن. اولین عنصر صف دو هستش. دو خونده میشه و فرزندان دو که چهار و پنج باشن به صف وارد میشن. اولین عنصر صف سه شده که خونده میشه و فرزندان اون یعنی شش و هفت وارد صف میشن. حالا چهار عنصر اول صف هست که خونده میشه و هشت و نه دارد میشه. عنصر بعدی پنج هست که خونده میشه و ده وارد میشه. عنصر بعدی شش هست که فرزندی نداره. پس فقط خونده میشه. همینطور هفت. عناصر بعدی هشت و نه و ده هستن که خوانده میشن بدون اضافه شدن فرزند. آخر سر صف خالی شده و الگوریتم تموم میشه.
NIMA_1981
جمعه 03 آذر 1391, 12:36 عصر
ممنون از زاهنمایی ایگه میشه این رو قدم به قدم با هم انجام بدیم - این ماتریس همین گراف بالا هستش
http://barnamenevis.org/asset.php?fid=91396&uid=28551&d=1353659394
حالا من باید از Stack استفاده کنم و اولین عنصر را اضافه کنم - اما یک مشکلی دیگه همیشه از عنصر بالا شروع نمیکنیم بعضی وقتی نقطه شورع مثلا میشه گره 5 -این مشکل باید چطوری حل کنم
با تشکر
مسعود اقدسی فام
جمعه 03 آذر 1391, 12:48 عصر
ممنون از زاهنمایی ایگه میشه این رو قدم به قدم با هم انجام بدیم - این ماتریس همین گراف بالا هستش
http://barnamenevis.org/asset.php?fid=91396&uid=28551&d=1353659394
حالا من باید از Stack استفاده کنم و اولین عنصر را اضافه کنم - اما یک مشکلی دیگه همیشه از عنصر بالا شروع نمیکنیم بعضی وقتی نقطه شورع مثلا میشه گره 5 -این مشکل باید چطوری حل کنم
با تشکر
برای پیمایش عمقی از پشته و برای پیمایش سطحی از صف استفاده میشه. به این نکته توجه کنید. من پستهای قبلی پیمایش سطحی bfs رو توضیح دادم. فکر کردم اون رو پرسیدید. در هر حال فرقی نمیکنه. dfs هم فرزندان به همون ترتیب وارد پشته میشن.
از هر گرهی شروع میکنید اون گره رو گره راس در نظر بگیرید. یعنی درخت رو طوری از نو رسم کنید که اون گره در راس قرار بگیره.
95465
البته این روش صرفا برای درک بهتر خودتونه. وگرنه از دید برنامه یه ماتریس مجاورتی وجود داره که ارتباط بین یالها رو مشخص میکنه.
vBulletin® v4.2.5, Copyright ©2000-1403, Jelsoft Enterprises Ltd.