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