رحلة مثيرة في عالم خوارزمية Depth First Search باستخدام PHP

العمق أولاً: فهم خوارزمية Depth First Search مع مثال توضيحي باستخدام PHP
 

مقدمة:

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

كيفية عمل Depth First Search:

تعتمد DFS على فكرة استكشاف الفرع الحالي حتى يتم استكشاف جميع فرعياته قبل التحرك إلى الفرع التالي. تُستخدم الاستدعاء الريكورسي بشكل شائع في تنفيذ هذه الخوارزمية، حيث يتم استكشاف الفرع قبل التحرك إلى الفرع التالي.

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

لفهم كيفية تنفيذ DFS في PHP، سنقوم بتقديم مثال توضيحي. لنفترض أن لدينا رسم بياني مكونًا من العقد التالية:
 

<?php

class Graph
{
    public $graph = array();
    public $visited = array();

    public function addEdge($start, $end)
    {
        $this->graph[$start][] = $end;
        $this->graph[$end][] = $start;
    }

    public function DFS($node)
    {
        echo $node . " ";
        $this->visited[$node] = true;

        foreach ($this->graph[$node] as $neighbor) {
            if (!$this->visited[$neighbor]) {
                $this->DFS($neighbor);
            }
        }
    }
}

// Create a graph and add edges
$myGraph = new Graph();
$myGraph->addEdge(1, 2);
$myGraph->addEdge(1, 3);
$myGraph->addEdge(2, 4);
$myGraph->addEdge(2, 5);
$myGraph->addEdge(3, 6);
$myGraph->addEdge(3, 7);

// Perform DFS starting from node 1
echo "DFS starting from node 1: ";
$myGraph->DFS(1);

?>

في هذا المثال، يتم إنشاء كائن من الصف Graph وتضاف الحواف باستخدام الدالة addEdge. ثم يتم تنفيذ DFS باستخدام الدالة DFS، حيث يتم طباعة العقد المستكشفة.

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

مقارنة هامه بين DFS و BFS من حيث آلية تصفح الأشجار :

لاحظ في الصورة التالية كيف تتصفح كل خوارزمية الشجره بدأً من العقدة A 
 

نذكر بأن :

خوارزمة BFS تعتمد في عملها على Queue أما خوارزمية DFS تعتمد على ال Stack 

BFS عادةً ما تستهلك مزيدًا من الذاكرة نظرًا لضرورة تخزين مستويات الأفرع في قائمة الانتظار.

DFS قد يستهلك أقل ذاكرة، ولكن قد يكون لديه تأثير جانبي في أداء الكود نظرًا لاستخدام الاستدعاء الريكورسي.