البحث المتعمق أولاً (DFS): دليل شامل لاستكشاف الرسوم البيانية مع أمثلة Leetcode

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

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

آلية عمل البحث المتعمق أولاً (DFS)

نظرًا لطبيعة DFS التكرارية (recursive)، يمكن تنفيذها باستخدام بنية بيانات المكدس (stack). إليك “التعويذة السحرية” لـ DFS:

• ادفع (Push) عقدة إلى المكدس (stack).
• اسحب (Pop) العقدة من المكدس.
• استرجع الجيران غير المزارين (unvisited neighbors) للعقدة التي تم سحبها، وادفعهم إلى المكدس.
• كرر الخطوات 1 و 2 و 3 طالما أن المكدس ليس فارغًا.

أنماط استكشاف الرسوم البيانية والأشجار الثنائية

بشكل عام، هناك ثلاثة أنماط أساسية لاستكشاف الأشجار الثنائية باستخدام DFS:

• الترتيب المسبق (Pre Order): الجذر (Root)، اليسار (Left)، اليمين (Right) أو الجذر، اليمين، اليسار.
• الترتيب اللاحق (Post Order): اليسار، اليمين، الجذر أو اليمين، اليسار، الجذر.
• الترتيب الوسطي (In Order): اليسار، الجذر، اليمين أو اليمين، الجذر، اليسار.

144. استكشاف شجرة ثنائية بترتيب مسبق (Binary Tree Preorder Traversal) (الصعوبة: متوسط)

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

في البداية، ندفع العقدة الجذرية (root node) إلى المكدس (stack). بينما المكدس ليس فارغًا، نسحب العقدة من المكدس، وندفع طفليها الأيمن والأيسر إلى المكدس. بمجرد سحب العقدة الجذرية، نضعها فورًا في قائمة النتائج لدينا. وبالتالي، يكون العنصر الأول في قائمة النتائج هو الجذر (ومن هنا جاء الاسم، Pre-order). العنصر التالي الذي سيتم سحبه من المكدس سيكون العنصر العلوي للمكدس حاليًا: الطفل الأيسر للعقدة الجذرية. تستمر العملية بطريقة مماثلة حتى يتم استكشاف الرسم البياني بالكامل وتدخل جميع قيم عقد الشجرة الثنائية في القائمة الناتجة.

145. استكشاف شجرة ثنائية بترتيب لاحق (Binary Tree Postorder Traversal) (الصعوبة: صعب)

استكشاف الترتيب المسبق (Pre-order traversal) هو جذر-يسار-يمين (root-left-right)، بينما الترتيب اللاحق (Post-order traversal) هو يمين-يسار-جذر (right-left-root). هذا يعني أن استكشاف الترتيب اللاحق هو بالضبط عكس استكشاف الترتيب المسبق. لذا، قد يتبادر إلى الذهن حل واحد وهو ببساطة عكس المصفوفة الناتجة من استكشاف الترتيب المسبق. ولكن فكر في الأمر – سيكلف ذلك تعقيدًا زمنيًا قدره O(n) لعكسها. الحل الأذكى هو نسخ ولصق الكود الدقيق لاستكشاف الترتيب المسبق، ولكن وضع النتيجة في بداية القائمة المتصلة (linked list) (المؤشر 0) في كل تكرار. يستغرق إضافة عنصر إلى رأس القائمة المتصلة وقتًا ثابتًا (O(1)). أليس هذا رائعًا؟

94. استكشاف شجرة ثنائية بترتيب وسطي (Binary Tree Inorder Traversal) (الصعوبة: متوسط)

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

323. عدد المكونات المتصلة في رسم بياني غير موجه (Number of Connected Components in an Undirected Graph) (الصعوبة: متوسط)

نهجنا هنا هو إنشاء متغير يسمى ans يخزن عدد المكونات المتصلة. أولاً، سنقوم بتهيئة جميع الرؤوس (vertices) على أنها غير مزورة (unvisited). سنبدأ من عقدة، وأثناء تنفيذ DFS على تلك العقدة (باستخدام “تعويذتنا السحرية” بالطبع)، ستقوم بتمييز جميع العقد المتصلة بها على أنها مزورة (visited). ستتم زيادة قيمة ans بمقدار 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<adj.length; i++){
 adj[i] = new ArrayList<Integer>();
 }
 // create the adjacency list
 for ( int [] e: edges){
 int from = e[ 0 ];
 int to = e[ 1 ];
 adj[from].add(to);
 adj[to].add(from);
 }
 Stack<Integer> stack = new Stack<>();
 int ans = 0 ;
 // ans = count of how many times DFS is carried out
 // this for loop through the entire graph
 for ( int i = 0 ; i < n; i++){
 // if a node is not visited
 if (!visited[i]){
 ans++;
 //push it in the stack
 stack.push(i);
 while (!stack.empty()) {
 int current = stack.peek();
 stack.pop();
 //pop the node
 visited[current] = true ; // mark the node as visited
 List<Integer> list1 = adj[current];
 // push the connected components of the current node into stack
 for ( int neighbours:list1) {
 if (!visited[neighbours]) {
 stack.push(neighbours);
 }
 }
 }
 }
 }
 return ans;
 }
 }

200. عدد الجزر (Number of Islands) (الصعوبة: متوسط)

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

547. دوائر الأصدقاء (Friend Circles) (الصعوبة: متوسط)

تتبع هذه المسألة أيضًا نفس المفهوم الخاص بإيجاد عدد المكونات المتصلة. في هذه المسألة، لدينا مصفوفة NxN ولكن فقط N من الأصدقاء إجمالاً. يتم إعطاء الحواف (edges) مباشرة عبر الخلايا، لذا يتعين علينا استكشاف صف للحصول على الجيران لصديق معين. لاحظ أننا هنا نستخدم نفس نمط المكدس (stack pattern) مثل مسائلنا السابقة.

الخلاصة التقنية

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