راهنمایی در مرود الگوریتم جستجوی عمق اول

[NIMA_1981]

سلام دوستان کسی الگوریتم dfs را بصورت غیر بازگستی میتونه بنویسه یا راهنمایی کنه که چطوری نوشته میشه

با تشکر

[مسعود اقدسی فام]

یه صف تعریف می‌کنید. هر عنصری رو که چاپ می‌کنید فرزندانش رو به ترتیب وارد صف می‌کنید. بعد اولین عنصر صف رو بر می‌دارید و همین کار رو تکرار می‌کنید. این عملیات تا زمانی انجام می‌شه که صف خالی بشه.

[NIMA_1981]

ممنون از راهنمایی خوب فرزندان رو چطوری وارد صف کنم بعد ممکنه خود اون فرزند بازم بچه داشته باشه میشه بیشتر راهنمایی کنید یا یک مثال بنویسید

با تشکر

[مسعود اقدسی فام]

ممنون از راهنمایی خوب فرزندان رو چطوری وارد صف کنم بعد ممکنه خود اون فرزند بازم بچه داشته باشه میشه بیشتر راهنمایی کنید یا یک مثال بنویسید

با تشکر

فرض کنید:



95387


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

[NIMA_1981]

ممنون از زاهنمایی ایگه میشه این رو قدم به قدم با هم انجام بدیم - این ماتریس همین گراف بالا هستش
http://barnamenevis.org/asset.php?fid=91396&uid=28551&d=1353659394
حالا من باید از Stack استفاده کنم و اولین عنصر را اضافه کنم - اما یک مشکلی دیگه همیشه از عنصر بالا شروع نمیکنیم بعضی وقتی نقطه شورع مثلا میشه گره 5 -این مشکل باید چطوری حل کنم
با تشکر

[مسعود اقدسی فام]

ممنون از زاهنمایی ایگه میشه این رو قدم به قدم با هم انجام بدیم - این ماتریس همین گراف بالا هستش
http://barnamenevis.org/asset.php?fid=91396&uid=28551&d=1353659394
حالا من باید از Stack استفاده کنم و اولین عنصر را اضافه کنم - اما یک مشکلی دیگه همیشه از عنصر بالا شروع نمیکنیم بعضی وقتی نقطه شورع مثلا میشه گره 5 -این مشکل باید چطوری حل کنم
با تشکر

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

از هر گرهی شروع می‌کنید اون گره رو گره راس در نظر بگیرید. یعنی درخت رو طوری از نو رسم کنید که اون گره در راس قرار بگیره.


95465


البته این روش صرفا برای درک بهتر خودتونه. وگرنه از دید برنامه یه ماتریس مجاورتی وجود داره که ارتباط بین یا‌ل‌ها رو مشخص می‌کنه.