در این مقاله، به بررسی عملیات جستجوی اول عمق (Depth-First Search) در گرافها میپردازیم. این الگوریتم یکی از روشهای مهم برای جستجوی راه حل در مسائل گرافی و درختی است که در بسیاری از موارد کاربرد دارد. در ادامه، به توضیحات بیشتری پیرامون این الگوریتم و نکات مهم مربوط به آن میپردازیم.
مقدمه
جستجوی اول عمق یکی از روشهای مهم جستجو در گرافها است که در آن از استراتژی “به سمت پایین برو” استفاده میشود. این الگوریتم ابتدا از یک رأس مشخص شروع میکند و به ازای هر رأس، به یکی از رئوس مجاور آن حرکت میکند و ادامه مسیر را پیش میبرد. این فرآیند تا زمانی که یک راه حل یا یک حالت مشخص برای مسئله پیدا شود یا تمام رئوس گراف بررسی شوند، ادامه مییابد.
اصول عملیات جستجوی اول عمق
- انتخاب رأس شروع: انتخاب یک رأس به عنوان نقطه شروع برای جستجو.
- انجام جستجو در عمق: شروع از رأس انتخاب می شود و ادامه عملیات جستجو در عمق گراف با انتخاب یکی از رئوس مجاور.
- بازگشت: در صورتی که دیگر رئوسی برای بررسی وجود نداشته باشد یا یک شرط مشخص برآورده شود، بازگشت به رأس قبلی و ادامه جستجو از آن نقطه.
- ادامه تا زمان پایان: تکرار مراحل 2 و 3 تا زمانی که یک راه حل یا یک حالت مورد نظر پیدا شود یا تمام رئوس گراف بررسی شوند.
مراحل عملیات جستجوی اول عمق
- اضافه کردن رأس شروع به پشته: رأس شروع به عنوان نخستین عضو پشته قرار میگیرد(در پشته عمل اضافه کردن و حذف عنصر، فقط در یک طرف آن، بنام بالای پشته انجام میشود. یعنی عنصری که از همه دیرتر وارد پشته شد، از همه زودتر از پشته حذف میگردد).
- بررسی رأس ابتدایی: رأس انتهایی از پشته خارج می شود و بررسی میشود.
- انجام عملیات: عملیات مربوط به رأس بررسی می شود (مانند چاپ یا ذخیره اطلاعات) انجام میشود.
- افزودن رئوس مجاور به پشته: رئوس مجاور به رأس بررسی شده اضافه می شود و فرآیند جستجو ادامه مییابد.
- تکرار مراحل: مراحل 2 تا 4 تا زمانی که پشته خالی شود، تکرار میشود.
مثال
تصویر زیر مربوط به یک گراف است:
اگر از راس 2 شروع کنیم. با توجه به عملیات DFS راس ها به صورت زیر است:
DFS: 2 1 0 4 3
- ابتدا راس 2 وارد پشته می شود (راس شروع)
- پشته در این مرحله: 2
- راس های مجاور را درون پشته می ریزیم یعنی 1 و 3. راس 2 بررسی و از پشته خارج میشود.
- پشته در این مرحله: 3 و 1
- یک راس از پشته خارج میکنیم (در پشته آخرین عنصر خارج میشود پس راس 1 برای بررسی انتخاب میشود).
- عملیات جستجو را از راس 1 انجام میدهیم.
- راس های مجاور را درون پشته می ریزیم. در این قسمت راس 0 و 4 نیز به پشته اضافه میشود. (راس 3 و 2 که در مجاورت راس 1 هستند قبلاً در پشته بوده به همین دلیل مجدداً به پشته اضافه نخواهند شد همچنین راس 1 از پشته خارج می شود).
- پشته در این مرحله: 3 و 4 و 0
- در این مرحله راس 0 انتخاب میشود.
- عملیات جستجو را از راس 0 انجام میدهیم.
- راس های مجاور را درون پشته می ریزیم. در این قسمت تمامی راس ها گراف درون پشته وارد می شود پس چیزی به پشته اضافه نمی شود.
- پشته در این مرحله: 3 و 4
- در این مرحله راس 4 انتخاب میشود.
- تمامی همسایه های این راس قبلاً بررسی شده پس به مرحله بعد می رویم.
- پشته در این مرحله: 3
- در این مرحله راس 3 انتخاب میشود.
- تمامی همسایههای این راس قبلاً بررسی شده پس به مرحله بعد میرویم.
- در این مرحله هیچ راس بررسی نشده در پشته وجود ندارد پس الگوریتم به پایان میرسد.
کاربردهای جستجوی اول عمق
- جستجوی مسیر: برای پیدا کردن مسیر بین دو رأس در گراف، به خصوص در الگوریتمهای روتیابی.
- جستجوی حالت در بازیهای رایانهای: در بازیهای مختلفی مانند بازیهای شطرنج یا پازل، جستجوی اول عمق برای پیدا کردن حالتهای مختلف بازی استفاده میشود.
- جستجوی توالیها: برای کشف توالیهای مرتبط با یک مسئله، مانند جستجوی الگوهای خاص در متون یا دادههای ساختار یافته.
نکات مهم
- الگوریتم جستجوی اول عمق در صورتی که گراف یا درخت بینهایت باشد ممکن است در یک حلقه گیر کند. برای رفع این مشکل میتوان از مجموعهای برای ذخیره رئوسی که قبلاً بررسی شدهاند، استفاده کرد.
- عملیات جستجوی اول عمق ممکن است نتیجه متفاوتی نسبت به جستجوی سایر الگوریتمها مانند جستجوی اول سطح (Breadth-First Search) داشته باشد.
نتیجهگیری
جستجوی اول عمق یکی از الگوریتمهای مهم در علوم کامپیوتر است که در حل مسائل مختلفی مانند جستجوی مسیر، حل بازیهای رایانهای و کشف توالیها استفاده میشود. با شناخت اصول، مراحل و کاربردهای جستجوی اول عمق، میتوان از این الگوریتم به بهترین شیوه ممکن برای حل مسائل مختلف استفاده کرد و به نتایج دقیق و مطلوب دست یافت.
