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

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

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

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

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

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

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

خوارزمية BFS تعتمد على استخدام هيكل بيانات يسمى الطابور (Queue) لاستكشاف العقد في طبقات. تعمل الخوارزمية على النحو التالي:

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

3. الحل في Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

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

4. الحل في Java

import java.util.*;

public class BFS {
    private Map<String, List<String>> graph = new HashMap<>();
    
    public void addEdge(String source, String destination) {
        graph.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
    }

    public void bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        visited.add(start);
        queue.add(start);
        
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (String neighbor : graph.getOrDefault(vertex, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

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

        System.out.println("BFS traversal starting from node A:");
        bfsGraph.bfs("A");
    }
}

5. الحل في C

#include <stdio.h>
#define MAX 5

void BFS(int graph[MAX][MAX], int start) {
    int visited[MAX] = {0};
    int queue[MAX], front = 0, rear = 0;

    printf("%d ", start);
    visited[start] = 1;
    queue[rear++] = start;

    while (front != rear) {
        int vertex = queue[front++];

        for (int i = 0; i < MAX; i++) {
            if (graph[vertex][i] == 1 && !visited[i]) {
                printf("%d ", i);
                visited[i] = 1;
                queue[rear++] = 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}
    };

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

    return 0;
}