مقاله‌ی اصلی: الگوریتم جستجوی اول عمق

الگوریتم جستجوی اول عمق یک روش ساده و در عین حال کارا برای مسیریابی است که در سال 1882 توسط ریاضی‌دان فرانسوی، چارلز پیر ترما به منظور حل هزارتوها پیشنهاد شد^[۱]. این الگوریتم بر پایه‌ی روش پس‌گرد استوار است^[۲][۳].

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

• گره پایانی مشاهده شود: در این حالت الگوریتم متوقف می‌شود و مسیر یافته شده به عنوان خروجی بازگردانده می‌شود.
• الگوریتم به خانه‌ای برسد که همسایه‌ی بازدید نشده ندارد: در این حالت الگوریتم یک قدم پس‌گرد می‌کند و یکی از گره‌هایی که در مرحله‌ی قبل بازدید نشده بود را بازدید می‌کند^[۴].

این الگوریتم را می‌توان به صورت تابع بازگشتی زیر در پایتون پیاده سازی کرد:

def depth_first_search(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        depth_first_search(graph, next, visited)
    return visited

مقاله‌ی اصلی: الگوریتم جستجوی اول سطح

این روش نخستین بار در سال 1959 توسط ادوارد مور برای یافتن کوتاه‌ترین مسیر در یک هزارتو معرفی شد^[۵]. با استفاده از این الگوریتم می‌توان کوتاه‌ترین مسیر بین دو راس از یک گراف غیر وزن دار را پیدا کرد.

در این روش که با استفاده از داده ساختار صف پیاده سازی می‌شود، قسمتی از گراف به عنوان جلودار (frontier) در نظر گرفته می‌شود. این قسمت از نقطه‌ی شروع آغاز به گسترش می‌نماید و بسته به کاربرد می‌تواند تا دربرگرفتن تمام گراف و یا تا حدی که نقطه‌ی پایان مسیر را شامل شود گسترش یابد. در صورت پیمایش تمام گراف، می توان مسیر بهینه را از نقطه‌ی شروع تا هر نقطه‌ی دلخواه دیگر را پیدا کرد.

این الگوریتم از یک حلقه‌ی تکرار با دو گام زیر تشکیل می‌شود و تا خالی شدن جلودار ادامه می‌یابد:

1. یک راس از جلودار را انتخاب کن و آن را حذف کن.
2. همسایه‌های راس حذف شده را در صورتی که در مجموع‌ بازدید شده‌ها (visited) نباشند به جلودار اضافه کن؛ همچنین این راس‌ها را در مجموعه‌ی بازدید شده‌ها قرار بده.

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

شبه کد الگوریتم به قرار زیر است.

frontier = Queue()
frontier.put(start )
visited = {}
visited[start] = True

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in visited:
         frontier.put(next)
         visited[next] = True

برای استفاده از الگوریتم‌های مسیریابی بایستی یک گراف در اختیار داشت؛ یعنی مجموعه‌ای از گره‌ها که به وسیله‌ی یال‌هایی (وزن‌دار یا بدون وزن) به یکدیگر متصلند. این گراف یا از ابتدا مشخص است، یا آنکه باید به طریقی آن را ایجاد کرد. الگوریتم‌های مسیریابی را می‌توان روی مشبکه‌ها نیز اجرا کرد. چرا که تمام مشبکه‌ها قابل تبدیل به گراف هستند. این الگوریتم‌ها باید اطلاعات زیر را داشته باشند:

• گره‌ها کدامند
• کدام گره‌ها به یکدیگر متصلند.

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

علاوه بر این، الگوریتم‌های مسیریابی برای شکل یک گراف اهمیتی قائل نیستند و در تمام گراف‌های یک‌ریخت به یک شیوه عمل می‌کنند. برای مثال دو گراف زیر از نظر الگوریتم‌های مسیریابی یکسان هستند.

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

1. ↑ j2kun (2013-01-22). "Depth- and Breadth-First Search". Math ∩ Programming (به انگلیسی). Retrieved 2019-12-05.
2. ↑ «Depth-First Search (DFS) | Brilliant Math & Science Wiki». brilliant.org (به انگلیسی). دریافت‌شده در ۲۰۱۹-۱۲-۰۵.
3. ↑ «3.5.2 Depth-First Search‣ 3.5 Uninformed Search Strategies ‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition». artint.info. دریافت‌شده در ۲۰۱۹-۱۲-۰۵.
4. ↑ Bettilyon, Tyler Elliot (2019-04-04). "Breadth First Search and Depth First Search". Medium (به انگلیسی). Retrieved 2019-12-05.
5. ↑ Moore, Edward F. (1959). "The shortest path through a maze". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292