استكشاف (Graph Search) خوارزمية بحث الرسم البياني في PHP

تعد خوارزمية Graph Search تقنية مهمة في برمجة PHP تُستخدم للعثور على المسارات أو الاتصالات بين الرؤوس في الرسم البياني. يعد هذا مفيدًا بشكل خاص عندما تحتاج إلى البحث عن أقصر مسار أو اتصال أو وجود علاقات داخل البيانات الممثلة ببنية الرسم البياني.

كيف تعمل خوارزمية بحث الرسم البياني

تتضمن خوارزمية Graph Search عادةً اجتياز رؤوس وحواف الرسم البياني للبحث عن معلومات محددة.

1. بدءًا من قمة المصدر: تبدأ الخوارزمية من قمة المصدر وتنتقل عبر الرؤوس المجاورة عبر الحواف للبحث عن رأس أو مسار الوجهة المطلوب.
2. البحث الأول(BFS) أو Depth-First Search(DFS): هناك طريقتان رئيسيتان لهذه الخوارزمية: Breadth-First Search(BFS) و Depth-First Search(DFS). يبحث BFS في الرؤوس المجاورة قبل الانتقال إلى المستوى التالي ، بينما يستكشف DFS بشكل أعمق في فرع قبل التراجع.
3. التحقق من قمة الوجهة: تتحقق الخوارزمية من وجود قمة أو علاقة الوجهة المطلوبة. إذا تم العثور عليها ، تقوم الخوارزمية بإرجاع النتيجة أو المسار المناسب.

مزايا وعيوب خوارزمية البحث في الرسم البياني

مزايا:

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

سلبيات:

• يعتمد الأداء على بنية الرسم البياني: يعتمد أداء الخوارزمية على هيكل الرسم البياني وحجمه.
• قدرة بحث محدودة: قد تكون الخوارزمية محدودة عند التعامل مع الرسوم البيانية الكبيرة والمعقدة.

المثال والشرح

تخيل أن لديك شبكة اجتماعية مع مستخدمين وتم تمثيل علاقاتهم في شكل رسم بياني. تريد تحديد ما إذا كان هناك اتصال بين المستخدم "أ" والمستخدم "ب" ، فيما يلي مثال لكيفية تنفيذ خوارزمية بحث الرسم البياني في PHP:

$graph = array(  
    'A' => array('B', 'C'),  
    'B' => array('A', 'D'),  
    'C' => array('A', 'E'),  
    'D' => array('B'),  
    'E' => array('C', 'F'),  
    'F' => array('E')  
);  
  
$startNode = 'A';  
$endNode = 'B';  
  
function searchGraph($graph, $start, $end) {  
    $visited = array();  
    $queue = new SplQueue();  
    $queue->enqueue($start);  
  
    while(!$queue->isEmpty()) {  
        $node = $queue->dequeue();  
  
        if(!isset($visited[$node])) {  
            $visited[$node] = true;  
  
            if($node === $end) {  
                return true;  
            }  
  
            foreach($graph[$node] as $neighbor) {  
                if(!isset($visited[$neighbor])) {  
                    $queue->enqueue($neighbor);  
                }  
            }  
        }  
    }  
  
    return false;  
}  
  
if(searchGraph($graph, $startNode, $endNode)) {  
    echo "There is a connection between $startNode and $endNode.";  
} else {  
    echo "There is no connection between $startNode and $endNode.";  
}  

في هذا المثال ، نقوم ببناء شبكة اجتماعية افتراضية باستخدام مصفوفة لمحاكاة البحث عن مسار بين مستخدمين داخل الشبكة. نحن نستخدم طريقة Breadth-First Search(BFS) للتنقل عبر الرؤوس والحواف للعثور على اتصال بين المستخدم A والمستخدم B. إذا تم العثور على اتصال ، فإن الخوارزمية ترجع النتيجة التي تشير إلى وجود علاقة بين المستخدمين ؛ وإلا ، فإنه يُبلغ عن عدم وجود علاقة.

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