بحث العمق أولاً: دليل اجتياز الرسم البياني DFS مع 6 أمثلة لـ Leetcode

هل سبق لك أن حللت متاهة حقيقية؟ النهج الذي يتبعه معظمنا أثناء حل المتاهة هو أننا نتبع مسارًا حتى نصل إلى طريق مسدود ، ثم نتراجع ونتتبع خطواتنا لإيجاد مسار آخر ممكن.

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

في البرنامج التعليمي اليوم ، سنكتشف نمط DFS الذي سيتم استخدامه لحل بعض الأسئلة المتعلقة بالشجرة والرسم البياني المهمة لمقابلة Tech Giant القادمة! سنحل بعض مشكلات Leetcode المتوسطة والصعبة باستخدام نفس التقنية الشائعة.

لذا ، لنبدأ ، أليس كذلك؟

التنفيذ

نظرًا لأن DFS له طبيعة تكرارية ، يمكن تنفيذه باستخدام مكدس.

سحر سحر DFS:

  1. ادفع عقدة إلى المكدس
  2. فرقع العقدة
  3. استرجع الجيران غير المرخص لهم للعقدة التي تمت إزالتها ، وادفعهم للتكدس
  4. كرر الخطوات 1 و 2 و 3 طالما أن المكدس ليس فارغًا

اجتياز الرسم البياني

بشكل عام ، هناك 3 عمليات اجتياز DFS أساسية للأشجار الثنائية:

  1. الطلب المسبق: الجذر ، اليسار ، اليمين أو الجذر ، اليمين ، اليسار
  2. طلب المشاركة: يسار ، يمين ، جذر أو يمين ، يسار ، جذر
  3. بالترتيب: يسار ، جذر ، يمين أو يمين ، جذر ، يسار

144 اجتياز الشجرة الثنائية للطلب المسبق (الصعوبة: متوسطة)

لحل هذا السؤال ، كل ما علينا فعله هو مجرد تذكر تعويذتنا السحرية. دعونا نفهم المحاكاة جيدًا لأن هذا هو النموذج الأساسي الذي سنستخدمه لحل بقية المشكلات.

في البداية ، ندفع عقدة الجذر إلى المكدس. في حين أن المكدس ليس فارغًا ، فإننا نخرجه ، وندفع الطفل الأيمن والأيسر إلى المكدس.

عندما نفتح عقدة الجذر ، نضعها على الفور في قائمة النتائج الخاصة بنا. وبالتالي ، فإن العنصر الأول في قائمة النتائج هو الجذر (ومن هنا جاء الاسم ، الطلب المسبق).

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

145. اجتياز الشجرة الثنائية بعد الطلب (الصعوبة: صعبة)

اجتياز الطلب المسبق هو الجذر - اليسار - اليمين ، والطلب اللاحق هو من اليمين - اليسار - الجذر . وهذا يعني أن اجتياز الطلب اللاحق هو بالضبط عكس اجتياز الطلب المسبق.

لذا فإن أحد الحلول التي قد يتبادر إلى الذهن الآن هو ببساطة عكس المصفوفة الناتجة من اجتياز الطلب المسبق. لكن فكر في الأمر - سيكلف ذلك تعقيد الوقت O (n) لعكسه.

الحل الأكثر ذكاءً هو نسخ ولصق الكود الدقيق لعملية اجتياز الطلب المسبق ، ولكن ضع النتيجة في أعلى القائمة المرتبطة (الفهرس 0) في كل تكرار. يستغرق الأمر وقتًا ثابتًا لإضافة عنصر إلى رأس قائمة مرتبطة. رائع ، أليس كذلك؟

94. اجتياز الشجرة الثنائية (الصعوبة: متوسطة)

نهجنا لحل هذه المشكلة يشبه المشاكل السابقة. لكن هنا ، سنزور كل شيء على الجانب الأيسر من العقدة ، ونطبع العقدة ، ثم نزور كل شيء على الجانب الأيمن من العقدة.

323. عدد المكونات المتصلة في رسم بياني غير موجه

(الصعوبة: متوسطة)

نهجنا هنا هو إنشاء متغير يسمى ans يخزن عدد المكونات المتصلة.

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

 import java.util.ArrayList; import java.util.List; import java.util.Stack; public class NumberOfConnectedComponents { public static void main(String[] args){ int[][] edge = {{0,1}, {1,2},{3,4}}; int n = 5; System.out.println(connectedcount(n, edge)); } public static int connectedcount(int n, int[][] edges) { boolean[] visited = new boolean[n]; List[] adj = new List[n]; for(int i=0; i
    

200. Number of Islands (Difficulty: Medium)

This falls under a general category of problems where we have to find the number of connected components, but the details are a bit tweaked.

Instinctually, you might think that once we find a “1” we initiate a new component. We do a DFS from that cell in all 4 directions (up, down, right, left) and reach all 1’s connected to that cell. All these 1's connected to each other belong to the same group, and thus, our value of count is incremented by 1. We mark these cells of 1's as visited and move on to count other connected components.

547. Friend Circles (Difficulty: Medium)

This also follows the same concept as finding the number of connected components. In this question, we have an NxN matrix but only N friends in total. Edges are directly given via the cells so we have to traverse a row to get the neighbors for a specific "friend".

Notice that here, we use the same stack pattern as our previous problems.

That's all for today! I hope this has helped you understand DFS better and that you have enjoyed the tutorial. Please recommend this post if you think it may be useful for someone else!