تعد Breadth First Search (BFS) إحدى تقنيات البحث الرئيسية في علم الحوسبة، وهي تُستخدم لاستكشاف وتحليل البيانات الهيكلية مثل الرسوم البيانية والأشجار. تمثل BFS خوارزمية فعّالة للعثور على أقصر مسار بين نقطتين في الرسم البياني، وتوفير حلاً للمشاكل التي تتطلب الاستكشاف التام للجيران قبل التحرك إلى الجيل التالي.

كيف يعمل BFS:

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

مثال عملي باستخدام PHP:

لنقم بتنفيذ خوارزمية BFS على رسم بياني بسيط باستخدام PHP. لدينا رسم بياني عبارة عن مصفوفة 2D:

<?php

function bfs($graph, $start, $end) {
    $queue = new SplQueue();
    $visited = [];
    $path = [];

    $queue->enqueue($start);
    $visited[$start] = true;

    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();

        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $queue->enqueue($neighbor);
                $visited[$neighbor] = true;
                $path[$neighbor] = $node;
            }
        }
    }

    if (!isset($path[$end])) {
        return null; // No path found
    }

    $shortestPath = [];
    $current = $end;

    while ($current !== $start) {
        $shortestPath[] = $current;
        $current = $path[$current];
    }

    $shortestPath[] = $start;
    $shortestPath = array_reverse($shortestPath);

    return $shortestPath;
}

// Example usage:
$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D', 'E'],
    'C' => ['A', 'F', 'G'],
    'D' => ['B'],
    'E' => ['B', 'H'],
    'F' => ['C'],
    'G' => ['C'],
    'H' => ['E'],
];

$startNode = 'A';
$endNode = 'G';

$result = bfs($graph, $startNode, $endNode);

if ($result) {
    echo 'Shortest path from ' . $startNode . ' to ' . $endNode . ': ' . implode(' -> ', $result);
} else {
    echo 'No path found from ' . $startNode . ' to ' . $endNode;
}

?>

Breadth First Search تعد أداة قوية في مجال الحوسبة، حيث تسهم في حل العديد من المشاكل المعقدة. يمكن استخدام الخوارزمية في مجالات متعددة مثل تحليل الشبكات، الألعاب، وتحسين أداء الروبوتات. الشيفرة البرمجية المرفقة توضح كيفية تنفيذ BFS باستخدام لغة PHP للعثور على أقصر مسار بين نقطتين في رسم بياني.