خوارزميات الرسوم البيانية للمقابلات التقنية: دليل عملي لفهم أهم الأنماط وحل الأسئلة بثقة

مقدمة: لماذا تُعد خوارزميات الرسوم البيانية مهمة في المقابلات التقنية؟

تُعد أسئلة هياكل البيانات والخوارزميات جزءاً أساسياً من معظم المقابلات البرمجية، وتأتي Graph Algorithms ضمن أكثر الموضوعات شيوعاً؛ لأنها تختبر فهمك للعلاقات بين العناصر، وقدرتك على التنقل بين المسارات، وتحليل التعقيد الزمني والفراغي للحل. إن امتلاك أساس قوي في هذا الباب يمنحك أفضلية واضحة عند التعامل مع مسائل مثل إيجاد المسار، واكتشاف المكوّنات المتصلة، وتحليل الجزر داخل الشبكات والمصفوفات.

هذا الدليل يقدّم شرحاً احترافياً ومبسّطاً لأهم أفكار الرسوم البيانية المستخدمة في المقابلات، مع التركيز على الأنماط العملية التي تتكرر كثيراً، بحيث تتمكن من تغطية نسبة كبيرة من الأسئلة الشائعة بثقة أكبر.

ما هو الرسم البياني في البرمجة؟

الرسم البياني أو Graph هو بنية بيانات تتكوّن من عنصرين أساسيين:

• العُقد أو Nodes: تمثل الكيانات أو العناصر.
• الحواف أو Edges: تمثل العلاقات أو الروابط بين هذه العناصر.

يمكنك تخيّل العقد على أنها مدن، والحواف على أنها طرق بين تلك المدن. كما يمكن أن تمثل العقد مقررات دراسية، وتمثل الحواف المتطلبات السابقة بين المقررات. لذلك، فالرسم البياني ليس مجرد شكل نظري، بل وسيلة قوية لنمذجة العلاقات في مسائل واقعية جداً.

العقدة والجارة والاتصال

عندما تكون هناك حافة تربط عقدتين، نقول إن كل واحدة منهما جارة للأخرى بحسب نوع الرسم البياني. ويُستخدم أحياناً مصطلح Vertex بدلاً من Node، وكلاهما صحيح.

الفرق بين الرسم الموجّه وغير الموجّه

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

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

كيف نُمثّل الرسم البياني داخل الكود؟

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

في لغة JavaScript مثلاً، غالباً ما نستخدم كائناً أو بنية Object لهذا الغرض، بينما يمكن استخدام Dictionary في Python أو Hash Map في لغات أخرى.

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

أهم خوارزميتين يجب إتقانهما: التمرير العمقي والعرضي

إذا كان هناك أساس واحد لا غنى عنه في الرسوم البيانية، فهو فهم التمرير أو Traversal. وأكثر نمطين شهرة هما:

• Depth First Search ويُختصر إلى DFS.
• Breadth First Search ويُختصر إلى BFS.

التمرير العمقي DFS

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

عادةً ما يُنفَّذ DFS باستخدام:

• Stack بشكل صريح.
• أو الاستدعاء الذاتي، حيث يعتمد النظام داخلياً على Call Stack.

التمرير العرضي BFS

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

عادةً ما يُنفَّذ BFS باستخدام Queue.

متى أستخدم DFS ومتى أستخدم BFS؟

تطبيق عملي: طباعة الرسم البياني باستخدام DFS وBFS

تنفيذ DFS بشكل تكراري في JavaScript

const depthFirstPrint = (graph, source) => {
  const stack = [source];

  while (stack.length > 0) {
    const current = stack.pop();
    console.log(current);

    for (let neighbor of graph[current]) {
      stack.push(neighbor);
    }
  }
};

في هذا المثال نستخدم stack.pop() لسحب آخر عنصر، ثم نضيف الجيران باستخدام stack.push(). ترتيب الجيران قد يغيّر ترتيب الإخراج، لكن النمط يظل صحيحاً بوصفه تمريراً عمقياً.

تنفيذ DFS بالاستدعاء الذاتي

const depthFirstPrint = (graph, source) => {
  console.log(source);

  for (let neighbor of graph[source]) {
    depthFirstPrint(graph, neighbor);
  }
};

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

تنفيذ BFS باستخدام الطابور

const breadthFirstPrint = (graph, source) => {
  const queue = [source];

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current);

    for (let neighbor of graph[current]) {
      queue.push(neighbor);
    }
  }
};

الاختلاف الأساسي هنا أن queue.shift() يسحب من البداية، بينما queue.push() يضيف إلى النهاية، وبذلك نحصل على ترتيب عرضي.

مسألة Has Path: هل يوجد مسار بين عقدتين؟

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

الفكرة العامة

يمكنك استخدام DFS أو BFS. إذا وصلت إلى العقدة الهدف، تُعيد true. وإذا انتهى الاستكشاف دون العثور عليها، تُعيد false.

حل باستخدام DFS التعاودي

const hasPath = (graph, source, destination) => {
  if (source === destination) return true;

  for (let neighbor of graph[source]) {
    if (hasPath(graph, neighbor, destination) === true) {
      return true;
    }
  }

  return false;
};

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

مسألة Undirected Path: إيجاد مسار في رسم غير موجّه

في هذه المسألة يكون الإدخال عادة على شكل قائمة حواف Edge List، لذا من الأفضل تحويلها أولاً إلى Adjacency List لتسهيل التمرير.

بناء الرسم من قائمة الحواف

const buildGraph = (edges) => {
  const graph = {};

  for (let [a, b] of edges) {
    if (!(a in graph)) graph[a] = [];
    if (!(b in graph)) graph[b] = [];
    graph[a].push(b);
    graph[b].push(a);
  }

  return graph;
};

أهمية مجموعة visited

في الرسوم غير الموجهة، يمكن الانتقال ذهاباً وإياباً بين العقد، ما قد يسبب حلقة لا نهائية إذا لم تمنع إعادة الزيارة. لهذا نستخدم Set لتتبع العقد التي سبق المرور بها.

const hasPath = (graph, source, destination, visited) => {
  if (source === destination) return true;
  if (visited.has(source)) return false;

  visited.add(source);

  for (let neighbor of graph[source]) {
    if (hasPath(graph, neighbor, destination, visited) === true) {
      return true;
    }
  }

  return false;
};

عدّ المكوّنات المتصلة Connected Components Count

المكوّن المتصل هو مجموعة من العقد التي يمكن الوصول بين أي عقدتين فيها عبر مسارات داخلية. والفكرة في هذه المسألة هي عدّ عدد تلك المجموعات داخل الرسم البياني.

منهجية الحل

1. أنشئ عداداً يبدأ من 0.
2. مرّ على جميع العقد.
3. عندما تصادف عقدة غير مزارة، ابدأ منها تمريراً كاملاً.
4. إذا نجح الاستكشاف في اكتشاف مكوّن جديد، زد العداد بمقدار واحد.

هذا النمط مهم جداً لأنه يتكرر في مسائل كثيرة، وليس فقط في الرسوم البيانية الكلاسيكية، بل أيضاً في مسائل الشبكات والمصفوفات.

إيجاد أكبر مكوّن Largest Component

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

عادةً ما تكون دالة الاستكشاف مسؤولة عن إعادة حجم المكوّن الحالي، ثم تُستخدم قيمة عظمى مثل largest أو maxSize لتخزين أفضل نتيجة حتى اللحظة.

أقصر مسار Shortest Path: لماذا يكون BFS هو الخيار الأفضل؟

حين يكون المطلوب هو أقل عدد من الحواف بين عقدتين في رسم غير موزون، فإن BFS هو الحل المنطقي؛ لأنه يستكشف العقد حسب بعدها عن نقطة البداية، لا حسب عمقها.

الفكرة العملية

نخزّن داخل الطابور زوجاً من القيم:

• العقدة الحالية.
• المسافة من نقطة البداية.

وعند الوصول إلى العقدة الهدف، تكون المسافة المخزنة هي طول أقصر مسار.

تنفيذ عملي

const shortestPath = (edges, nodeA, nodeB) => {
  const graph = buildGraph(edges);
  const visited = new Set([nodeA]);
  const queue = [[nodeA, 0]];

  while (queue.length > 0) {
    const [node, distance] = queue.shift();

    if (node === nodeB) return distance;

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }

  return -1;
};

إذا لم يوجد مسار بين العقدتين، فمن المعتاد إعادة القيمة -1.

مسائل الشبكات الثنائية الأبعاد: عدّ الجزر Island Count

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

كيف نحول الشبكة إلى فكرة رسم بياني؟

كل موضع يمكن تمثيله بزوج (row, col). ومن هذا الموضع توجد حتى أربعة تحركات ممكنة:

• أعلى: (row - 1, col)
• أسفل: (row + 1, col)
• يسار: (row, col - 1)
• يمين: (row, col + 1)

خطوات الحل

1. استخدم حلقتين متداخلتين للمرور على جميع الخلايا.
2. عند العثور على خلية أرض Land غير مزارة، ابدأ منها استكشافاً كاملاً.
3. بعد انتهاء الاستكشاف، زد عدد الجزر بمقدار واحد.

هنا أيضاً تُستخدم مجموعة visited لتفادي إعادة العد أو الوقوع في دورة.

إيجاد أصغر جزيرة Minimum Island

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

فكرة مهمة في التنفيذ

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

const exploreSize = (grid, row, col, visited) => {
  const rowInBounds = 0 <= row && row < grid.length;
  const colInBounds = 0 <= col && col < grid[0].length;

  if (!rowInBounds || !colInBounds) return 0;
  if (grid[row][col] === 'W') return 0;

  const pos = row + ',' + col;
  if (visited.has(pos)) return 0;
  visited.add(pos);

  let size = 1;
  size += exploreSize(grid, row - 1, col, visited);
  size += exploreSize(grid, row + 1, col, visited);
  size += exploreSize(grid, row, col - 1, visited);
  size += exploreSize(grid, row, col + 1, visited);

  return size;
};

تحليل التعقيد الزمني والفراغي

من المهم جداً في المقابلات ألا تكتفي بكتابة الحل، بل تشرح كفاءته أيضاً.

في الرسوم البيانية التقليدية

إذا رمزنا إلى عدد العقد بـ n وعدد الحواف بـ e، فإن كثيراً من مسائل التمرير تعتمد على:

• تعقيد زمني: O(e) أو أحياناً O(n + e) بحسب طريقة العرض والتحليل.
• تعقيد فراغي: O(n).

في مسائل الشبكات Grid

إذا كان لدينا r صفوف وc أعمدة، فغالباً يكون:

• التعقيد الزمني: O(r * c)
• التعقيد الفراغي: O(r * c)

السبب أن كل خلية تُزار في أسوأ الأحوال مرة واحدة فقط.

أفضل النصائح لاجتياز أسئلة الرسوم البيانية في المقابلات

• ابدأ دائماً برسم الشكل يدوياً حتى لو كان الإدخال عبارة عن Adjacency List.
• حدّد بسرعة: هل الرسم موجّه أم غير موجّه؟ وهل يحتوي على دورات؟
• اسأل نفسك مبكراً: هل أحتاج visited؟ في معظم الرسوم غير الموجهة، الإجابة نعم.
• إذا كان السؤال عن أقصر مسار في رسم غير موزون، فابدأ التفكير بـ BFS.
• إذا كان السؤال عن استكشاف مكوّن أو حساب حجمه، فغالباً يناسبه DFS.
• تدرّب على تحويل Edge List إلى Adjacency List بسرعة.
• انتبه عند العمل على الشبكات إلى حدود الصفوف والأعمدة قبل الوصول إلى العناصر.

محاور أساسية ينبغي إتقانها

• أساسيات الرسم البياني وتمثيله.
• التمرير العمقي DFS والتمرير العرضي BFS.
• التحقق من وجود مسار بين عقدتين.
• التعامل مع الرسوم غير الموجهة والدورات.
• عدّ المكوّنات المتصلة.
• إيجاد أكبر مكوّن.
• إيجاد أقصر مسار.
• حل مسائل الجزر في الشبكات الثنائية الأبعاد.
• استخراج أصغر جزيرة أو أكبر جزيرة عبر الاستكشاف التعاودي.

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

خوارزميات الرسوم البيانية ليست موضوعاً معزولاً، بل هي مجموعة أنماط متكررة تظهر بصيغ مختلفة في المقابلات التقنية. بمجرد إتقانك لأساسيات DFS وBFS، وفهمك العميق لفكرة visited، وتمثيل البيانات عبر Adjacency List أو الشبكات الثنائية الأبعاد، ستتمكن من حل عدد كبير من المسائل التي تبدو معقدة للوهلة الأولى. الرأي التقني الأهم هنا هو أن النجاح لا يعتمد على حفظ الحلول، بل على التعرف إلى النمط الصحيح بسرعة، ثم تكييفه مع صيغة السؤال بثقة ووضوح.