شرح Depth-First Search (DFS) – الحل في Python، Java، وC

1. مقدمة عن المشكلة

وصف المشكلة:
خوارزمية البحث بالعمق (Depth-First Search) هي تقنية تُستخدم للبحث أو استكشاف العقد في الرسم البياني أو الشجرة. تبدأ هذه الخوارزمية من عقدة البداية وتستكشف قدر الإمكان على طول كل فرع قبل التراجع.

حالة استخدام:
تُستخدم DFS في العديد من التطبيقات، مثل إيجاد المسارات في المتاهات، تحليل الشبكات الاجتماعية، واختبار الدورات في الرسوم البيانية.

المدخلات والمخرجات:

• المدخلات: رسم بياني أو شجرة وعقدة بداية.
• المخرجات: تسلسل العقد التي تم استكشافها.

2. شرح تعليمي للحل

خوارزمية DFS تعتمد على استخدام هيكل بيانات يسمى المكدس (Stack)، والذي يمكن تطبيقه باستخدام الاستدعاء الذاتي (recursion) أو صراحةً باستخدام هيكل المكدس.

• نبدأ من عقدة البداية ونقوم بوضعها في المكدس.
• نقوم بزيارة العقدة، وإذا كانت تحتوي على عقد غير مستكشفة، نضيفها إلى المكدس.
• نكرر العملية حتى يتم استكشاف جميع العقد الممكنة.
• في كل مرة نصل إلى عقدة بدون عقد مجاورة لم يتم زيارتها، نقوم بالتراجع.

3. الحل في Python

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for next in graph[start] - visited:
        dfs(graph, next, visited)

# استخدام المثال
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}
print("DFS traversal starting from node A:")
dfs(graph, 'A')

4. الحل في Java

import java.util.*;

public class DFS {
    private Map<String, List<String>> graph = new HashMap<>();
    private Set<String> visited = new HashSet<>();

    public void addEdge(String source, String destination) {
        graph.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
    }

    public void dfs(String start) {
        if (!visited.contains(start)) {
            visited.add(start);
            System.out.print(start + " ");
            for (String neighbor : graph.getOrDefault(start, Collections.emptyList())) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        DFS dfsGraph = new DFS();
        dfsGraph.addEdge("A", "B");
        dfsGraph.addEdge("A", "C");
        dfsGraph.addEdge("B", "D");
        dfsGraph.addEdge("B", "E");
        dfsGraph.addEdge("C", "F");
        dfsGraph.addEdge("E", "F");

        System.out.println("DFS traversal starting from node A:");
        dfsGraph.dfs("A");
    }
}

5. الحل في C

#include <stdio.h>
#define MAX 5

void DFS(int graph[MAX][MAX], int visited[MAX], int start) {
    printf("%d ", start);
    visited[start] = 1;

    for (int i = 0; i < MAX; i++) {
        if (graph[start][i] == 1 && !visited[i]) {
            DFS(graph, visited, i);
        }
    }
}

int main() {
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 1, 1, 1, 0}
    };
    int visited[MAX] = {0};

    printf("DFS traversal starting from node 0:\n");
    DFS(graph, visited, 0);

    return 0;
}