خوارزمية بحث بالعمق أولا DFS

مفهوم خوارزمية البحث بالعمق أولا DFS:

خوارزمية البحث بالعمق أولاً (Depth First Search)، وهي خوارزمية تبحث في الرسم البياني(Graph) بطريقة منظمة باستخدام الاستدعاء الذاتي (recursion)، و تنطوي هذه الخوارزمية على عملية البحث الشامل لجميع العقد (nodes)، وذلك من خلال البحث “أعمق” في الرسم البياني كلما أمكن ذلك، وان لم تتمكن نقوم بالتراجع (backtrack).

وتعني كلمة التراجع (backtrack) أنه عندما تتقدم للأمام ولا توجد عقد (nodes) أخرى على طول المسار الحالي، فإنك تتحرك للخلف على نفس المسار للعثور على العقد (nodes) التي لم يتم زيارتها بعد، وبعد زيارة جميع العقد (nodes) على المسار الحالي واجتيازها جميعاً، يتم تحديد المسار التالي وزيارة العقد فيه بنفس الطريقة.

طريقة عمل خوارزمية البحث بالعمق أولا DFS:

تبدأ خوارزمية (DFS) من عقدة البداية (a)، في كل خطوة، تختار الخوارزمية واحدة من العقد التي لم تتم زيارتها من بين العقد المجاورة للعقدة (a)، على سبيل المثال، أن العقدة(a) متصلة ب (b)، تنفذ الخوارزمية استدعاء متكرر يبدأ من العقدة (b)، وعندما تتم زيارة جميع جيران العقد (b)، تقوم الخوارزمية بالعودة للعقدة (a) و للتحقق من جيرانها الباقين واللذين لم تتم زيارتهم بعد.

وعلى عكس خوارزمية البحث بالعرض أولاً (BFS)، لا تزور خوارزمية ال (DFS) العُقد على أساس المستوى تلو المستوى الأخر. بدلاً من ذلك، تستمر في التعمق قدر الإمكان، وبمجرد أن تصل الخوارزمية إلى نهايتها، فإنها تحاول التعمق أكثر باستخدام العقد الأخرى المتصلة بها  والتي لم تمت زيارتها بعد.

مثال على آلية عمل خوارزمية البحث بالعمق أولا DFS:

لنفترض أننا سنبدأ عملية (DFS) من العقدة (S)، ولنفترض أن جميع العقد المجاورة داخل قائمة مرتبة أبجديًا. سنجري العمليات التالية:

• بدءًا من العقدة (S)، فإنها متصلة بالعقدتين (A و B).

• نتابع من العقدة (A)، نظرًا لأن العقدة (A) تجاور عقدة واحد لم تتم زيارتها وهي (F)، فإننا نستمر منها.

• تتصل العقدة (F) بعقدتين، لم تتم زيارتهما وهما (D و E)، فنواصل العمل من العقدة (D).

• العقدة (D)، متصلة بعقدة واحد ولم تتم زيارته بعد، وهي العقدة (B). لذلك، فنواصل العمل إلى (B).

• وبالمثل، تتصل العقدة (B) بعقدة واحدة لم تتم زيارتها، وهي العقدة (C). لذلك، يجب أن تكون العقدة التالية هي (C). لاحظ أن العقدة (B) متصلة أيضًا بالعقدتين (S و D)، لكن، تمت زيارتهم بالفعل.

• لدى العقدة (C) فقط العقدة (E)، والتي لم تتم زيارتها بعد. بالتالي، ننتقل إلى (E).

• أخيرًا ، لا تحتوي العقدة (C) على أي جيران لم تتم زيارتها. ستتراجع الخوارزمية إلى (C) و (B) و (D) و (F) و (A) ثم (S). لن تحتوي هذه العقد على أي عناصر متصلة بها و لم تتم زيارتها. لذلك، تنتهي الخوارزمية ببساطة.

• نتيجة لذلك ، فإن الترتيب النهائي للعقد التي تمت زيارتها ابتدئاً من (S)، هم: (ِA, F, D, B, C, E).

تعقيد الوقت complexity time لخوارزمية البحث بالعمق أولا:

يتم تمثيل التعقيد الزمني لخوارزمية (DFS) في شكل “O(V+E)”، حيث (V) هو عدد العقد، و (E) هو عدد الحواف، السبب وراء هذا، هو أننا نزور كل عقدة مرة واحدة فقط بواسطة دالة (DFS)، وكل عقدة نقوم بزيارة سنزور العقد المتصلة، لذلك، سوف نستكشف كل حافة (edge) داخل الرسم البياني مرتين. لنفترض أن الحافة بين (a) و (b)، فلأول مرة، نستكشف بأن العقدة (a) بأنها متصلة بالعقدة (b)، بينما في المرة الثانية، اكتشفنا أن العقدة (b) متصلة بالعقدة (a). لذلك

تطبيق عملي على خوارزمية البحث بالعمق أولا:

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

المدخلات:

يتكون السطر الأول من عددين صحيحين هما (n و m)، حيث أن ( n، m ≤ 10^5) ، والتي تمثل عدد القرى وعدد الطرق بينها ، على التوالي، يحتوي كل سطر من سطور (m) التالية على عددين صحيحين هما (a و b)، حيث أن (a ≠ b) و ( a, b ≤ n)، أي أن كل خط يعني أن هناك طريقًا مباشرًا بين القرية (a) و (b). ملاحظة: قد يكون هناك عدة طرق بين نفس الزوج من القرى.

المخرجات:

اطبع عددًا صحيحًا واحدًا وهو حل المشكلة.

مثال:

المدخلات:

4 3
1 2
2 3
3 2

المخرجات:

1

الحل: