سری پنجم: گراف‌ها (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 #الگوریتم_گراف #آموزش_تلگرام