آموزش الگوریتم جستجوی عمق‌اول (Depth-First Search - DFS)

مقدمه:

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

مراحل اجرای DFS:

1. شروع از گره مبدا:

از یک گره مشخص (مثلاً start) شروع می‌کنیم.

2. بازدید از گره‌ها:

گره فعلی را بازدید کرده و آن را به لیست گره‌های بازدید شده اضافه می‌کنیم.

3. حرکت به گره‌های همسایه:

به یکی از گره‌های همسایه که هنوز بازدید نشده است حرکت می‌کنیم و از همانجا دوباره مراحل 1 و 2 را اجرا می‌کنیم.

4. بازگشت به عقب:

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

5. پایان:

این فرآیند تا زمانی که تمامی گره‌ها بازدید شوند ادامه می‌یابد.

پیاده‌سازی DFS در پایتون:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()  # مجموعه‌ای برای نگهداری گره‌های بازدید شده
    visited.add(start)  # افزودن گره فعلی به مجموعه بازدید شده‌ها
    print(start)  # چاپ گره بازدید شده (می‌توانید این قسمت را به دلخواه تغییر دهید)

    for neighbor in graph[start]:  # بررسی همسایه‌های گره فعلی
        if neighbor not in visited:  # اگر همسایه هنوز بازدید نشده بود
            dfs(graph, neighbor, visited)  # بازگشتی برای بازدید از همسایه
    return visited  # بازگرداندن مجموعه گره‌های بازدید شده

مثال عملی:

فرض کنید یک گراف به شکل زیر داریم:

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

برای اجرای الگوریتم DFS از گره 'A'، کد زیر را اجرا می‌کنیم:

visited_nodes = dfs(graph, 'A')
print("Visited Nodes:", visited_nodes)

توضیحات:

در این مثال، الگوریتم DFS از گره 'A' شروع کرده و به ترتیب به گره‌های 'B'، 'D'، 'E' و 'F' می‌رود.

مزایا و معایب الگوریتم DFS:

مزایا:

- پیاده‌سازی ساده و مستقیم.
- مصرف حافظه کمتر نسبت به الگوریتم جستجوی عرض‌اول (BFS) برای گراف‌های بزرگ.

معایب:

- ممکن است به عمق بسیار زیادی برود (به خصوص در گراف‌های بزرگ و عمیق).
- در برخی موارد، تمام مسیرها را پیمایش می‌کند و ممکن است بهینه نباشد.

🟥برای یاد گرفتن الگوریتم های بیشتر اینجا کلیک کن🟥

#DFS #Python #GraphAlgorithm #پایتون #الگوریتم #برنامه‌نویسی

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۳: الگوریتم‌های جستجو در گراف‌ها 🔍

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم اصلی جستجو در گراف‌ها می‌پردازیم: جستجوی عمق‌اول (DFS) و جستجوی پهنای‌اول (BFS). این الگوریتم‌ها ابزارهای اساسی برای پیمایش و تحلیل گراف‌ها هستند. 🚀

الگوریتم‌های جستجو در گراف‌ها 🧩

۱. جستجوی عمق‌اول (Depth-First Search - DFS) 🌲

- تعریف: الگوریتم جستجوی عمق‌اول برای پیمایش یا جستجوی در گراف به روش عمق‌محور عمل می‌کند. این الگوریتم به ترتیب در عمق گراف جستجو می‌کند و تا زمانی که به گره‌ای نرسد که دیگر هیچ گره فرزند نداشته باشد، به پیشروی ادامه می‌دهد.

- ویژگی‌ها:
- پیاده‌سازی: می‌تواند با استفاده از پشته یا بازگشت پیاده‌سازی شود.
- کاربردها: یافتن مسیرها، بررسی اتصال، الگوریتم‌های بازیابی، و حل معماها.

- پیاده‌سازی DFS:

  def dfs(graph, start, visited=None):
      if visited is None:
          visited = set()
      visited.add(start)
      print(start)
      for neighbor in graph[start]:
          if neighbor not in visited:
              dfs(graph, neighbor, visited)
      return visited
  

- مثال:

برای گراف زیر:

  A -- B -- C
  |    |
  D -- E
  

اجرای dfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, C, E, D.

۲. جستجوی پهنای‌اول (Breadth-First Search - BFS) 🌐

- تعریف: الگوریتم جستجوی پهنای‌اول برای پیمایش گراف به روش سطح‌محور عمل می‌کند. این الگوریتم از یک گره شروع کرده و به ترتیب به گره‌های همسایه آن سطح به سطح جستجو می‌کند.

- ویژگی‌ها:
- پیاده‌سازی: با استفاده از صف پیاده‌سازی می‌شود.
- کاربردها: یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن، الگوریتم‌های بهینه‌سازی، و حل معماهای جغرافیایی.

- پیاده‌سازی BFS:

  from collections import deque

  def bfs(graph, start):
      visited = set()
      queue = deque([start])
      while queue:
          vertex = queue.popleft()
          if vertex not in visited:
              print(vertex)
              visited.add(vertex)
              queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
      return visited
  

- مثال:

برای همان گراف:

  A -- B -- C
  |    |
  D -- E
  

اجرای bfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, D, C, E.

مقایسه DFS و BFS 🔍

- DFS:
- مزایا: می‌تواند مسیرهای طولانی و پیچیده را سریعاً پیدا کند.
- معایب: ممکن است گراف‌های بزرگ را به صورت عمیق جستجو کند و به حافظه زیادی نیاز داشته باشد.

- BFS:
- مزایا: مناسب برای یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن.
- معایب: ممکن است حافظه بیشتری نسبت به DFS نیاز داشته باشد به دلیل ذخیره‌ی تمام گره‌های سطحی.


در این پارت، الگوریتم‌های جستجو در گراف‌ها یعنی DFS و BFS را بررسی کردیم. در پارت بعدی، به الگوریتم‌های جستجوی کوتاه‌ترین مسیر در گراف‌ها خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#جستجوی_عمق_اول #جستجوی_پهنای_اول #DFS #BFS #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

پارت 2: الگوریتم‌های پیمایش گراف
یکی از مهم‌ترین بخش‌های کار با گراف‌ها، پیمایش (Traversal) است. با پیمایش گراف می‌توان به اطلاعات مختلف دست یافت، مانند:
- بررسی اتصال رأس‌ها (🔗).
- یافتن مسیر بین رأس‌ها (🚶‍♂️).
- تحلیل داده‌های گراف (📊).



🎯 انواع پیمایش گراف:
1. پیمایش عرضی (BFS - Breadth First Search):
- گراف را به صورت لایه‌لایه (📏) پیمایش می‌کند.
- از یک رأس شروع کرده و ابتدا رأس‌های مجاور را بررسی می‌کند.
- مناسب برای پیدا کردن کوتاه‌ترین مسیر.

💡 مراحل BFS:
1. رأس شروع را در یک صف (Queue) قرار دهید.
2. رأس جاری را بازدید کرده و رأس‌های مجاور را به صف اضافه کنید.
3. تا خالی شدن صف، مراحل را تکرار کنید.

✨ کد BFS در پایتون:

   from collections import deque

   def bfs(graph, start):
       visited = set()
       queue = deque([start])
       while queue:
           node = queue.popleft()
           if node not in visited:
               print(node, end=" ")
               visited.add(node)
               queue.extend(graph[node])

   # تعریف گراف
   graph = {
       '1': ['2', '3'],
       '2': ['4', '5'],
       '3': ['6'],
       '4': [],
       '5': [],
       '6': []
   }
   print("BFS:", end=" ")
   bfs(graph, '1')
   

2. پیمایش عمقی (DFS - Depth First Search):
- گراف را به صورت عمقی (🔍) پیمایش می‌کند.
- ابتدا رأس شروع و سپس رأس‌های فرزندان هر رأس بررسی می‌شوند.
- مناسب برای بررسی تمام مسیرهای ممکن.

💡 مراحل DFS:
1. رأس شروع را به یک پشته (Stack) اضافه کنید.
2. رأس جاری را بازدید کرده و رأس‌های فرزند را به پشته اضافه کنید.
3. تا خالی شدن پشته، مراحل را تکرار کنید.

✨ کد DFS در پایتون:

   def dfs(graph, start, visited=None):
       if visited is None:
           visited = set()
       visited.add(start)
       print(start, end=" ")
       for neighbor in graph[start]:
           if neighbor not in visited:
               dfs(graph, neighbor, visited)

   # تعریف گراف
   graph = {
       '1': ['2', '3'],
       '2': ['4', '5'],
       '3': ['6'],
       '4': [],
       '5': [],
       '6': []
   }
   print("DFS:", end=" ")
   dfs(graph, '1')
   

📚 جمع‌بندی:
- BFS برای پیدا کردن کوتاه‌ترین مسیر مناسب است.
- DFS برای جستجوی عمیق و بررسی همه مسیرها به‌کار می‌رود.
در پارت بعدی با الگوریتم‌های پیشرفته مثل دایکسترا و درخت پوشای کمینه آشنا خواهیم شد.


#پیمایش_گراف #BFS #DFS #الگوریتم_گراف #آموزش_تلگرام