انتقال للمقال
فهرس المحتويات

مقدمة دخولك لعالم الجراف | Graph Theory

السلام عليكم ورحمة الله وبركاته

وقت القراءة: ≈ 25 دقيقة (بمعدل فنجان واحد من القهوة 😊)

المقدمة

سنبدأ اليوم في شرح واحد من أهم المواضيع في عالم البرمجة وهو الجراف Graph، وهو يعد أهم وأكبر هياكل البيانات Data Structure في عالم البرمجة، وهو يستخدم في العديد من المجالات مثل الشبكات والألعاب والذكاء الصناعي والتعلم الآلي والعديد من المجالات الأخرى

هذه المقالة ستكون أكبر من مجرد مقدمة بل ستكون مفصلة قليلًا وستشمل عدة مواضيع منها مقدمة عن الجراف ثم تعريف لشكله وأهم المصطلحات التي تحوم حوله
ثم سنتعرف على كيفية بناء الجراف والبحث فيه وأهم الخوارزميات المتعلقة به ومنها الـ BFS والـ DFS
وسنعطي بعض الأمثلة العملية على كيفية استخدام الجراف في البرمجة

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

ما هو الجراف ؟

الجراف هو مجموعة من الـ Nodes والـ Edges، والمقصود بالـ Node هو العنصر التي يتم تخزينه وتمثيله في الجراف
أما الـ Edge الرابطة بين كل Node والآخر
الـ Node يمكن أن يكون أي شيء يمكنك تخيله مثل رقم أو حرف أو object أو أي شيء آخر

    user_1 ---------> user_2
      |                 |
      |                 |
      v                 |
    user_3            user_4

هذا الشكل يمثل جراف بسيط يحتوي على 4 أشخاص وكل شخص يمثل Node
ويوجد 3 روابط بينهم كما تلاحظ كل رابطة تمثل Edge

وستلاحظ أن كل Node يمكنه أن يكون له أكثر من Edge وباتجاهات مختلفة
بمعنى هنا لدينا user_1 يمكنه التواصل مع user_2 و user_3 ولكن العكس لا
وهذا يعني أن الـ Edge يكون له اتجاه معين
وستلاحظ أن user_2 و user_4 يمكنهم التواصل مع بعضهما البعض لأن الـ Edge التي تربطهما تكون بدون اتجاه معين أي كأنها ذهاب وإياب

الجراف بشكل عام يمثل شبكة من الروابط بين العناصر المختلفة
وهو يعد من أقوى الهياكل البيانات المسؤولة عن تحزين البيانات بشكل مترابط ومتصل بينها كما سترى لاحقًا

العناصر التي تخزن في الجراف تسمى Node والروابط بينها تسمى Edge
والـ Edge يمكن أن يكون له اتجاه معين ويسمى Directed Edge ويمكن أن يكون بدون اتجاه معين ويسمى Undirected Edge

كيفية بناء الجراف في البرمجة ؟

في البرمجة يمكننا تمثيل الجراف بطريقتين رئيسيتين وهما:

  • Adjacency Matrix
  • Adjacency List

الـ Adjacency Matrix يمثل الجراف بشكل مصفوفة ثنائية الأبعاد 2D Array
والـ Adjacency List يمثل الجراف بشكل Linked List
وسنتعرف على كل منهما بشكل مفصل

Adjacency Matrix

الـ Adjacency Matrix ما هي إلا أراي ثنائية الأبعاد تستخدم كمحاولة لتمثيل الجراف

    user_1 ---------> user_2
      |                 |
      |                 |
      v                 |
    user_3            user_4

فهنا يمكنا تخيل أن كل شخص يمثل رقمًا معينًا مثل user_1 يمثل 0 و user_2 يمثل 1 وهكذا

user_1 --> 0
user_2 --> 1
user_3 --> 2
user_4 --> 3

بالتالي يمكننا أن نقول أن هناك Edge بين 0 و 1 وهي user_1 و user_2
و Edge بين 0 و 2 وهي user_1 و user_3 وهكذا

حسنًا كيف نمثل هذه الروابط في الـ Adjacency Matrix ؟

أولًا لننشيء أراي ثنائية الأبعاد بحجم 4x4 ورقم 4 يمثل عدد الـ Node
وهذه الأراي ستكون قيمها من نوع boolean بالتالي كل عنصر فيها سيكون true أو false
وهذا سنستفيد منه لتحديد وجود رابطة بين Node والآخر أم لا

const graph: boolean[][] = [
  [false, false, false, false],
  [false, false, false, false],
  [false, false, false, false],
  [false, false, false, false],
];

الآن أنشأنا الـ Adjacency Matrix وحاليًا كل قيمها false وهذا يعني أنه لا يوجد رابطة بين أي Node
الآن كيف سنقوم بإضافة الروابط ؟ كيف سنقول أن هناك رابطة بين user_1 و user_2 ؟

ببساطة تتذكر حينما قلنا لنفترض أن كل شخص يمثل رقمًا معينًا ؟
بالتالي user_1 يمثل الرقم 0 و user_2 يمثل الرقم 1
هكذا عندما نقوم أن هناك رابطة من user_1 إلى user_2 فهذا أن هناك Edge من 0 إلى 1

بالتالي كل ما علينا فعله هو تغيير قيمة الـ graph[0][1] إلى true

graph[0][1] = true;

هكذا قلنا أن هناك رابطة من 0 إلى 1
وهذه الرابطة اتجاه واحد فقط من user_1 إلى user_2 وليس العكس
وهذا يعني أن user_1 يمكنه التواصل مع user_2 ولكن العكس لا

لنعد للجراف السابق ونقوم بتمثيله في الـ Adjacency Matrix

    user_1 ---------> user_2
      |                 |
      |                 |
      v                 |
    user_3            user_4

هذا الجراف يستخدم object لتمثيل الـ Node ولكن نستطيع تمثيله بأرقام كما قلنا سابقًا لتبسيط الأمور


      0 --------------> 1
      |                 |
      |                 |
      v                 |
      2                 3

والآن لاحظ وركز على الـ Adjacency Matrix الخاص بنا وكيف لنملئه بالبيانات ونمثل الجراف فيه

graph[0][1] = true;
graph[0][2] = true;
graph[1][3] = true;
graph[3][1] = true;

هكذا قمنا بتمثيل الجراف في الـ Adjacency Matrix
نحن لم نقم بشيء سوى تغيير قيمة الـ index المحدد في الـ Adjacency Matrix إلى true لتمثيل الـ Edge بين الـ Node
فمثلًا graph[0][1] = true يعني أن هناك Edge بين 0 و 1 وهذا يعني أن user_1 يمكنه التواصل مع user_2
و graph[0][2] = true يعني أن هناك Edge بين 0 و 2 وهذا يعني أن user_1 يمكنه التواصل مع user_3
و graph[1][3] = true يعني أن هناك Edge بين 1 و 3 وهذا يعني أن user_2 يمكنه التواصل مع user_4
و graph[3][1] = true يعني أن هناك Edge بين 3 و 1 وهذا يعني أن user_4 يمكنه التواصل مع user_2

وهكذا يمكنك بسهولة أن تعرف إذا كان هناك Edge بين Node والآخر أم لا
الآن شكل الـ Adjacency Matrix الخاص بنا سيكون كالتالي

i \ j 0 1 2 3
0 false true true false
1 false false false true
2 false false false false
3 false true false false

هكذا يمكنك ببساطة أن تتفقد أي عنصر في الـ Adjacency Matrix وتعرف إذا كان هناك Edge بين Node والآخر أم لا بكل سهولة

شكل الـ Adjacency Matrix في النهاية سيكون كالتالي
هناك تطبيقات مفيدة للـ Adjacency Matrix سنتطرق لها لاحقًا
لكن لاحظ أن هذه الطريقة رغم أنها سهلة وبسيطة إلا أنها تستهلك الكثير من الذاكرة

فتخيل لو لدينا 1000 شخص، كم سيكون حجم الـ Adjacency Matrix ؟
سيكون 1000x1000 وهذا يعني أنه سيكون لدينا 1000000 خانة مليون خانة تحتوي على قيمة true أو false
وبشكل مبدئي سيكون لديك كل القيم بـ false قبل أن يكون لديك حتى أي روابط
بمعنى أننا نستهلك الكثير من الذاكرة بدون فائدة
وهذا يعتبر عيب كبير في الـ Adjacency Matrix لذا لا يستخدم كثيرًا في البرمجة

تطبيق عملي صغير لتسجيل القيم في الـ Adjacency Matrix

غالبًا عندما تتعامل مع الجراف سيكون دائمًا مع قائمة من الـ Node والـ Edge التي تريد تسجيلها في الـ Adjacency Matrix
والـ Node يمكن أن يكون رقم أو حرف أو object أو أي شيء آخر
والـ Edge هي الروابط بين الـ Node والآخر

فغالبا ما ستكون لديك بيانات مسبقة عن البيانات التي تريد تسجيلها بهذا الشكل

const users = [
  { id: 0, name: 'user_1' },
  { id: 1, name: 'user_2' },
  { id: 2, name: 'user_3' },
  { id: 3, name: 'user_4' },
  { id: 4, name: 'user_5' },
];

const relations = [
  { from: 0, to: 2 },
  { from: 0, to: 3 },
  { from: 1, to: 0 },
  { from: 2, to: 1 },
  { from: 3, to: 4 },
  { from: 4, to: 0 },
];

لاحظ مثلًا هنا لدينا 5 أشخاص و 6 روابط بينهم
هنا يمكنك اعتماد أن الأشخاص يمثلون الـ Node وسنستخدم الـ id لتمثيلهم
والروابط بينهم تمثل الـ Edge وعن طريق from و to نستطيع معرفة من يستطيع التواصل مع من

الآن سنقوم بتسجيل هذه البيانات في الـ Adjacency Matrix

طبعًا نحتاج أولًا لإنشاء الـ Adjacency Matrix وهنا سنقوم بتسجيل القيم بـ false لكل العناصر
وهنا أنا فقط استخدم لغة الـ TypeScript لكن يمكنك استخدام أي لغة برمجية تفضلها

// Create the graph (matrix 2D) with false values
const graph: boolean[][] = Array.from({ length: users.length }, () =>
  Array(users.length).fill(false)
);

شكل الـ Adjacency Matrix حاليًا سيكون فارغًا وكل قيمة فيه false

i \ j 0 1 2 3 4
0 false false false false false
1 false false false false false
2 false false false false false
3 false false false false false
4 false false false false false

الآن بعد أن أنشأنا الـ Adjacency Matrix سنقوم بتسجيل الروابط فيه

for (let i = 0; i < relations.length; i++) {
  let from = relations[i].from;
  let to = relations[i].to;

  graph[from][to] = true;
}

لاحظ أننا فقط نقوم بعمل for loop على الـ relations التي تمثل كل رابطة فيها Edge
ثم نستخدم from و to لتحديد أي Node يمكنه التواصل مع الآخر
وفي النهاية نقوم بتسجيل القيمة true في الـ Adjacency Matrix لتحديد وجود الـ Edge هكذا graph[from][to] = true
هكذا قمنا بتسجيل الروابط في الـ Adjacency Matrix بكل سهولة

Adjacency List

طريقة أخرى لتمثيل الجراف هي الـ Adjacency List وهي تستخدم Linked List لتمثيل الجراف
وتعد الطريقة الأكثر استخدامًا في البرمجة لتمثيل الجراف لأنه يحجز فقط الذاكرة اللازمة للروابط فقط
بمعنى لو لدينا 1000 شخص فسيتم حجز فقط 1000 خانة في الذاكرة
ولوكل شخص يملك رابطة أي Edge مع شخص آخر فسيتم حجز هذه Edge فقط

يمكنك تخيل الـ Adjacency List كأنها أراي من الـ Linked List
بمعنى أن كل عنصر أو index في الأراي يمثل Linked List خاص به

لنتخيل الأمر بالمثال الخاص بنا الذي يحتوي على 4 أشخاص والذي نمثلهم بالأرقام من 0 إلى 3

      0 --------------> 1
      |                 |
      |                 |
      v                 |
      2                 3

الآن الـ 0 ما هو إلا Node أليس كذلك ؟
وهذه الـ Node يمكنها التواصل مع 1 و 2
فهنا كأن الرقم 0 يمثل Linked List يحتوي على 1 و 2
والـ 1 يمثل Linked List يحتوي على 3
والـ 2 يمثل Linked List فارغة لأنه لا يوجد Edge بين 2 وأي Node أو العكس
والرقم 3 يمثل Linked List يحتوي على 1

0 : 1 -> 2
1 : 3
2 :
3 : 1

لنقم بتمثيل الجراف السابق في الـ Adjacency List
وهنا سنقوم بإنشاء أراي من الـ Linked List

وبالطبع إن كنت قد قرأت مقالة LinkedList كبديل مرن وقوي للـ Array فيمكنك استخدامها لتعريف الجراف بطريقة الـ Adjacency List هكذا

const graph: LinkedList[] = Array.from(
  { length: 4 },
  () => new LinkedList()
);

الآن لدينا أراي فارغة وكل عنصر فيها يمثل Linked List فارغة حاليًا
بالطبع أنت تستخدم اللغة البرمجية التي تدعم الـ Linked List
في الـ C++ يمكنك استخدام vector وفي الـ Java يمكنك استخدام ArrayList
وفي الـ TypeScript يمكنك استخدام الـ الأراي العادية وهكذا
بالرفم من أنني أظن أنها أقرب إلى كونها Dynamic Array أكثر من الـ Linked List في بعض اللغات البرمجية مثل الـ C++

الآن بعد ما أنشأنا الـ Adjacency List سواء بالـ Array أو الـ LinkedList سنقوم بتسجيل الروابط فيه
لاحظ شيء هنا أن الجراف هو أراي من الـ Linked List وكل index في الأراي يمثل Linked List خاص به

بمعنى أن graph[0] يمثل Linked List خاص بـ 0
و graph[1] يمثل Linked List خاص بـ 1
و graph[2] يمثل Linked List خاص بـ 2
وهكذا ...

تذكر الشكل السابق للجراف الخاص بنا

      0 --------------> 1
      |                 |
      |                 |
      v                 |
      2                 3

أولًا سنقوم بإضافة الـ Edge بين 0 و 1 وسنضيف أيضا واحد بين 0 و 2

graph[0].push(1);
graph[0].push(2);

لاحظ أننا استخدمنا الدالة push لإضافة عنصر جديد إلى الـ Linked List الخاص بـ 0
و 0 هنا هو الـ index في الأراي الرئيسية لكننا نستخدمه كـ Node لذا نقوم بإضافة الـ Edge إليه

لآن أصبح الـ Adjacency List الخاص بنا يبدو كالتالي

0 : 1 -> 2
1 :
2 :
3 :

الآن سنقوم بإضافة الـ Edge بين 1 و 3 وسنضيف أيضا واحد بين 3 و 1

graph[1].push(3);
graph[3].push(1);

بما أن الـ Edge ليس له اتجاه معين فهذا يعني أنه يمكن لـ 1 التواصل مع 3 والعكس
لذا اضفنا الـ Edge بينهما في الـ Adjacency List

والآن الـ Adjacency List الخاص بنا يبدو كالتالي

0 : 1 -> 2
1 : 3
2 :
3 : 1

هكذا قمنا بتمثيل الجراف في الـ Adjacency List بنجاح

وهذه الطريقة تعتبر الأكثر استخدامًا في البرمجة لتمثيل الجراف لأنها تستهلك القليل من الذاكرة
لكن الاختلاف هنا أنك في الـ Adjacency Matrix إذا أردت أن تعرف إذا كان هناك Edge بين Node والآخر فكل ما عليك فعله هو البحث في الـ index المحدد هكذا

let from = 0;
let to = 1;

if (graph[from][to]) {
  // There is an edge between 0 and 1
}

لكن في الـ Adjacency List يجب عليك البحث في الـ Linked List الخاص بالـ Node وهذا يستهلك القليل من الوقت

let from = 0;
let to = 1;

if (graph[from].isExist(to)) {
  // There is an edge between 0 and 1
}

لاحظ أننا هنا قمنا بالبحث في الـ Linked List الخاص بـ 0 ونقول إذا كان يحتوي على 1 أم لا
باستخدام دالة isExist التي تقوم بالبحث عن القيمة المحددة في الـ Linked List
لأنه تذكر أن graph[0] يمثل Linked List لذا لا يدعم مفهوم الـ index مباشرة كما في الـ Adjacency Matrix
لذا عليك انشاء دالة تقوم بالبحث في الـ Linked List الخاص بـ Node لتعرف إذا كان هناك Edge بينهم أم لا
لذا افترضنا أن هناك دالة isExist تقوم بالبحث في الـ Linked List وتعيد true أو false حسب النتيجة

ويمكنك تخيل الدالة بهذا الشكل

class LinkedList {
  // ..

  public isExist(value: number): boolean {
    let current = this.head;

    while (current != null) {
      if (current.value === value) {
        return true;
      }

      current = current.next;
    }

    return false;
  }
}

لذا ستلاحظ بالطبع أن الـ Adjacency List قد تستهلك بعض الوقت في البحث عن الـ Edge بين الـ Node مقارنة بالـ Adjacency Matrix

تطبيق عملي صغير لتسجيل القيم في الـ Adjacency List

لنستمر على على نفس النهج ونقوم بتسجل البيانات التالية في الـ Adjacency List
كما في المثال السابق والذي كان يقول أنه لدينا بضعة أشخاص وعدد من الروابط بينهم

const users = [
  { id: 0, name: 'user_1' },
  { id: 1, name: 'user_2' },
  { id: 2, name: 'user_3' },
  { id: 3, name: 'user_4' },
  { id: 4, name: 'user_5' },
];

const relations = [
  { from: 0, to: 2 },
  { from: 0, to: 3 },
  { from: 1, to: 0 },
  { from: 2, to: 1 },
  { from: 3, to: 4 },
  { from: 4, to: 0 },
];

أولًا سنقوم بإنشاء الـ Adjacency List الخاص بنا
بحسب اللغة التي تستخدمها ستكون الطريقة مختلفة وكما قلت سابقًا هنا أنا استخدم الـ TypeScript

// Create the graph (array of Linked List) with empty values
const graph: LinkedList[] = Array.from(
  { length: users.length },
  () => new LinkedList()
);

الآن بعد أن أنشأنا الـ Adjacency List سنقوم بتسجيل الروابط فيه

for (let i = 0; i < relations.length; i++) {
  let from = relations[i].from;
  let to = relations[i].to;

  graph[from].push(to);
}

نفس الطريقة السابقة نقوم بعمل for loop على الـ relations ونقوم بتسجيل الروابط في الـ Adjacency List
وكما عرفنا أن كل index في الأراي يمثل Linked List ونحن فقط نقوم بإضافة الـ Edge إليه
عن طريق push كما في الشرح السابق

هكذا قمنا بتسجيل الروابط في الـ Adjacency List بكل سهولة

شكل الجراف سيكون كالتالي:

0 : 2 -> 3
1 : 0
2 : 1
3 : 4
4 : 0

هكذا قمنا بتمثيل الجراف في الـ Adjacency List بنجاح

وزيادة تأكيد بأنك سجلت وبنيت الـ Adjacency List بشكل صحيح يمكنك أن تقوم بطباعة الـ Linked List الخاصة بكل Node

for (let i = 0; i < graph.length; i++) {
  console.log('Node ' + i);
  for (let node = graph[i].head; node != null; node = node.next) {
    console.log('Connected to ' + node.value);
  }
}

هنا نحن نلف على الـ graph بحكم أنها أراي من الـ Linked List
ونقوم بطباعة الـ Node الحالية ثم نلف على الـ Linked List الخاصة بهذه الـ Node لنطبع الـ Node التي يمكنه التواصل معها

البحث في الجراف

البحث في الجراف يعتبر من أهم العمليات التي يمكن أن تقوم بها في الجراف
ويوجد الكثير والكثير من الطرق للبحث في الجراف ومنها:

  • BFS (Breadth First Search) أيضًا معروف بـ Shortest Path First وهو يبحث عن أقصر مسار بين نقطتين
    ويعتمد على مفهوم الـ Queue في التخزين والبحث
  • DFS (Depth First Search) وهو أيضًا يبحث عن مسار معين بين نقطتين لكنه مختلف عن الـ BFS
    وميزته أنه يعتمد على مفهوم الـ Backtracking
    ويعتمد على مفهوم الـ Stack في التخزين والبحث
  • Dijkstra وهو يبحث عن أقصر مسار بين نقطتين ويعتبر من أهم الخوارزميات في الجراف
    ويعتمد على مفهوم الـ Greedy Algorithm
    لكنه يعمل على الجراف الذي يحتوي على أوزان Weighted Graph وسنتعرف عليه لاحقًا في مقالة مستقلة
  • A* وهو يعتبر من أهم الخوارزميات في الذكاء الصناعي والتعلم الآلي
    وهو نسخة مطورة من الـ Dijkstra ويعتمد على مفهوم الـ Heuristic
    يجب أن تكون المكان الذي تريد الوصول إليه معلومة مسبقًا
    وسنتعرف عليه لاحقًا في مقالة مستقلة أيضًا
  • ... والعديد والعديد من الخوارزميات الأخرى

هنا في هذه المقالة سنتعرف على الـ BFS والـ DFS فقط

الـ BFS هو خوارزمية بحث تعتمد على مفهوم الـ Queue
والذي شرحناه في مقالة الـ Queue وكيفية بناءه بالـ LinkedList

الـ BFS هو أسلوب بحث يركز على أقصر مسافة بين الـ Node والأخرى
بمعنى أنه يبدأ من الـ Node الحالية التي تقف عليها ثم ينتقل إلى كل الـ Node المجاورة لها
وعندما يمر على كل الـ Node المجاورة لها ينتقل إلى الـ Node المجاورة لها وهكذا حتى يصل إلى الـ Node المطلوب

لنأخذ مثالًا بسيطًا لفهم الـ BFS

              user_5      user_2      user_6
                |           |           |
                |           |           |
  user_9 ---- user_1 ---- user_0 ---- user_3 ---- user_10
                |           |           |
                |           |           |
              user_8      user_4      user_7

هذا الجراف يحتوي على 11 شخص وهم متصلين ببعضهم البعض
ولاحظ أن كل شخص لديه تواصل أو معارف مع بعض الأشخاص الآخرين
فالشخص الذي يمثل user_0 يمكنه التواصل مع user_1 و user_2 و user_3 و user_4
والشخص الذي يمثل user_1 يمكنه التواصل مع user_0 و user_5 و user_8 و user_9
وهكذا ...

لنتخيل أننا نقف عند الـ user_0 ونريد الوصول إلى الـ user_8
لكننا لا نعرف أين يقع الـ user_8 بالضبط

وقررنا استخدام الـ BFS للوصول إلى الـ user_8
ما يفعله الـ BFS كما قلنا أنه يبدأ من الـ Node الحالية ثم ينتقل إلى كل الـ Node المجاورة لها
لذا نحن بدأنا من الـ user_0 ثم ما سنفعله هو أننا سننتقل إلى كل الأشخاص المجاورين لـ user_0
ونرى هل user_8 موجود بينهم أم لا
كأنك تبحث عن شخص معين في الحي الذي تعيش فيه وتسأل كل جار لديك هل رأيت هذا الشخص أم لا
فالـ BFS يعمل بنفس الطريقة فهو يبدأ بالجيران الذي يحيطون بك أولًا

بالتالي الخطواط التي سيتبعها الـ BFS للوصول إلى الـ user_8 ستكون كالتالي

يبدأ من الـ user_0 ويرى هل الـ user_0 هو من نبحث عنه ؟
الاجابة لا لذا سنبحث ونرى جيرانه وهما user_1 و user_2 و user_3 و user_4
الـ BFS سيضيف هؤلاء الأشخاص إلى Queue ويبدأ بالبحث فيهم بالترتيب
لأن الـ Queue يعمل بنظام FIFO أي أن الأول الذي يدخل هو الأول الذي يخرج
وهذا ما نريده لأننا نريد البحث بالترتيب
بحيث أننا نريد أن نبحث في الجيران الأقرب إلينا أولًا ثم ننتقل إلى الجيران الأبعد عنا
هنا نحن نبحث في الجيران الأقرب إلى الـ user_0 أولًا وهم user_1 و user_2 و user_3 و user_4

Queue: [user_1, user_2, user_3, user_4]

ونبدأ بالبحث في الـ user_1 ونرى هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنخرجه من الـ Queue ونرى الاشخاص الأخرين وهم user_2 و user_3 و user_4
لكن قبل أن نخرج الـ user_1 من الـ Queue سنقوم بإضافة جيرانه إلى الـ Queue لنبحث فيهم لاحقًا
جيران الـ user_1 هم user_0 و user_5 و user_8 و user_9

Queue: [user_2, user_3, user_4, user_0, user_5, user_8, user_9]

لكن انتظر لحظة ستلاحظ أننا أضفنا الـ user_0 إلى الـ Queue وهذا خطأ لأننا قد بحثنا فيه من قبل
لذا لا نريد أن بحث فيه مرة أخرى لذا لكي نتجنب تكرار البحث في نفس الـ Node مرتين
يمكننا إنشاء أراي بسيطة تدعى visited على سبيل المثال ونقوم بتسجيل الـ Node التي قمنا بالبحث فيها

بالتالي عندما ننتهي من التحقق من أي الـ Node نقوم بتسجيله في الـ visited
وأيضًا قبل أن نضع أي Node جديدة في الـ Queue نقوم بالتحقق من الـ visited أولًا هل تم البحث فيها من قبل أم لا

الآن شكل الـ Queue و visited سيكون كالتالي

Queue: [user_2, user_3, user_4, user_5, user_8, user_9]
Visited: [user_0, user_1]

لنراجع ما حصل
أولًا بدأنا من الـ user_0 وبحثنا فيه ووجدنا أنه ليس الـ user_8 الذي نبحث عنه
ثم وضعناه في الـ visited لأننا قد بحثنا فيه
ثم بدأنا بالبحث في جيرانه وهم user_1 و user_2 و user_3 و user_4
ووضعناهم في الـ Queue وبدأنا بالبحث فيهم
بدأنا بالبحث في الـ user_1 ووجدنا أنه ليس الـ user_8 الذي نبحث عنه
لذا بوضعه في الـ visited
ثم وضعنا جيرانه في الـ Queue وهم user_0 و user_5 و user_8 و user_9
لكننا استثنينا الـ user_0 لأننا قد بحثنا فيه من قبل وهو موجود في الـ visited

حتى حصلنا على الشكل التالي

Queue: [user_2, user_3, user_4, user_5, user_8, user_9]
Visited: [user_0, user_1]

هل لاحظ شيء أخر ؟
جيران الـ user_1 هم user_0 و user_5 و user_8 و user_9
تم وضعهم في الـ Queue ولكننا لن نبحث فيهم الآن
بل نبحث بالترتيب لذا سنبدأ بالبحث في الـ user_2 وهكذا

ونسأل هل الـ user_2 هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنخرجه من الـ Queue ونضع جيرانه في الـ Queue لكن ستجد أن user_0 هو جار الـ user_2 الوحيد
لكن بالطبع لقد بحثنا في الـ user_0 من قبل لذالن نضعه في الـ Queue
وبالطبع نضع الـ user_2 في الـ visited لأننا قد بحثنا فيه

ونكمل البحث في الـ user_3 ونسأل هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنخرجه من الـ Queue ونضع جيرانه في الـ Queue وهم user_6 و user_10 و user_7 ما عدا الـ user_0
ونضع الـ user_3 في الـ visited لأننا قد بحثنا فيه

ونكمل البحث في الـ user_4 ونسأل هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنخرجه من الـ Queue ونضع جيرانه في الـ Queue لكن سنجد أيضًا أن الـ user_1 هو جار الـ user_4 الوحيد لذا لن نضعه في الـ Queue
ثم نضع الـ user_4 في الـ visited لأننا قد بحثنا فيه

الآن شكل الـ Queue و visited سيكون كالتالي

Queue: [user_5, user_8, user_9, user_6, user_10, user_7]
Visited: [user_0, user_1, user_2, user_3, user_4]

لاحظ أننا انتهينا من البحث في الـ user_0 وجيرانه وهم user_1 و user_2 و user_3 و user_4
ثم الآن سنتقل إلى الـ user_5 وهو أحد جيران الـ user_1
لاحظ كيف أن اسلوب البحث في الـ BFS يعمل بالترتيب ويبدأ بالجيران الأقرب إليك أولًا
ثم عندما ينتهي من البحث في الجيران الأقرب إليك ينتقل إلى الجيران الأبعد عنك وهكذا

الآن سنكمل البحث في الـ user_5 ونسأل هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنخرجه من الـ Queue ونضع جيرانه في الـ Queue والذي يكون user_1 فقط
لكننا لن نضعه في الـ Queue لأننا قد بحثنا فيه من قبل
ونضع الـ user_5 في الـ visited لأننا قد بحثنا فيه

ونكمل البحث في الـ user_8 ونسأل هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة نعم لذا سننهي البحث

هكذا وصلنا إلى الـ user_8 بنجاح عن طريق user_0 باستخدام الـ BFS
هذا هو الـ BFS بشكل بسيط وسهل

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

تطبيق عملي للـ BFS

لنقم بتطبيق الـ BFS على الجراف السابق

أولًا سنقوم بإنشاء الجراف وتسجيل الروابط فيه كما في الشرح السابق

const users = [
  { id: 0, name: 'user_0' },
  { id: 1, name: 'user_1' },
  { id: 2, name: 'user_2' },
  { id: 3, name: 'user_3' },
  { id: 4, name: 'user_4' },
  { id: 5, name: 'user_5' },
  { id: 6, name: 'user_6' },
  { id: 7, name: 'user_7' },
  { id: 8, name: 'user_8' },
  { id: 9, name: 'user_9' },
  { id: 10, name: 'user_10' },
];

const relations = [
  { from: 0, to: 1 },
  { from: 0, to: 2 },
  { from: 0, to: 3 },
  { from: 0, to: 4 },
  { from: 1, to: 0 },
  { from: 1, to: 5 },
  { from: 1, to: 8 },
  { from: 1, to: 9 },
  { from: 2, to: 0 },
  { from: 3, to: 0 },
  { from: 3, to: 6 },
  { from: 3, to: 7 },
  { from: 3, to: 10 },
  { from: 4, to: 0 },
  { from: 5, to: 1 },
  { from: 6, to: 3 },
  { from: 7, to: 3 },
  { from: 8, to: 1 },
  { from: 9, to: 1 },
  { from: 10, to: 3 },
];

ثم سنقوم بإنشاء الـ Adjacency List وتسجيل الروابط فيه

const graph: LinkedList[] = Array.from(
  { length: users.length },
  () => new LinkedList()
);

for (let i = 0; i < relations.length; i++) {
  let from = relations[i].from;
  let to = relations[i].to;

  graph[from].push(to);
}

الآن سنقوم بكتابة دالة الـ BFS

function bfs(graph: LinkedList[], start: number, target: number): boolean {
  let queue: Queue = new Queue();
  let visited: boolean[] = Array.from(
    { length: graph.length },
    () => false
  );

  queue.push(start);
  visited[start] = true;

  while (queue.length > 0) {
    let current = queue.pop();

    if (current === target) {
      return true;
    }

    for (let node = graph[current].head; node != null; node = node.next) {
      if (!visited[node.value]) {
        queue.push(node.value);
        visited[node.value] = true;
      }
    }
  }

  return false;
}

هنا قمنا بكتابة دالة الـ BFS
وسنشرحها بالتفصيل قليلًا وستلاحظ أنها مثل ما شرحناها سابقًا
يمكنك قراءتها وفهمها بنفسك إن أردت

قبل أن نشرحها سنقوم بتجربتها

bfs(graph, 0, 8); // true

هنا قمنا بتجربة الـ BFS ونرى هل يمكننا الوصول من الـ user_0 إلى الـ user_8 أم لا
والنتيجة كانت true لذا يمكننا الوصول من الـ user_0 إلى الـ user_8
يمكنك تعديل الدالة لتجعلها ترجع لك الـ Node التي يمكنك الوصول إليها
أو المسار الذي يمكنك الوصول إليها

الآن سنشرح الدالة

أولًا قمنا بإنشاء الـ Queue والـ visited
وبدأنا بوضع الـ start في الـ Queue وجعلناه visited

let queue: Queue = new Queue();
let visited: boolean[] = Array.from({ length: graph.length }, () => false);

queue.push(start);
visited[start] = true;

وفي حالتنا هنا الـ start هو الـ user_0

ثم بدأنا بالـ while loop ونقوم بالبحث في الـ Queue
ونقوم بإخراج أخر Node دخلت الـ Queue ونرى هل هو الـ target الذي نبحث عنه ؟

while (queue.length > 0) {
  let current = queue.pop();

  if (current === target) {
    return true;
  }

  // ...

إذا كان الـ current هو الـ target الذي نبحث عنه نرجع true
لكن بالطبع حاليًا الـ current هو الـ user_0 وليس الـ target الذي نبحث عنه والذي هو الـ user_8
في حالة أن الـ current هو الـ target نرجع true وننهي البحث

وفي حالة أن الـ current ليس الـ target نقوم بالبحث في جيرانه
ونضعهم في الـ Queue ونجعلهم visited

for (let node = graph[current].head; node != null; node = node.next) {
  if (!visited[node.value]) {
    queue.push(node.value);
    visited[node.value] = true;
  }
}

حاليًا الـ current هو الـ user_0 ونبحث في جيرانه وهم user_1 و user_2 و user_3 و user_4
وكلهم ليسو visited لذا نضعهم في الـ Queue ونجعلهم visited
كما ترى في الشرط if (!visited[node.value]) والذي يتحقق من أن الـ Node هل تم البحث فيه من قبل أم لا
لكي لا نكرر البحث في نفس الـ Node مرتين والذي سيأدي إلى حدوث Infinite Loop

هكذا نكمل البحث حتى نصل إلى الـ target أو حتى ننتهي من الـ Queue
إذا وجدنا الـ target نرجع true وإذا أنهينا الـ Queue ولم نجد الـ target نرجع false

هذا هو الـ BFS بشكل بسيط وسهل

الـ DFS هو خوارزمية بحث تعتمد على مفهوم الـ Stack (يمكننا أيضًا استخدام الـ Recursion لتطبيقه)
لكننا في هذا المثال سنستخدم الـ Stack البسيط ويمكنك قراءة مقالة الـ Stack وكيفية بناءه بالـ LinkedList لفهم كيفية بناء الـ Stack وأسلوب عمله

على عكس الـ BFS الذي كان يبحث أولًا في الجيران الأقرب إليك ثم ينتقل إلى الجيران الأبعد عنك
يقوم الـ DFS بالبحث في العمق أولًا بمعنى أنه يبدأ من الـ Node الحالية ثم ينتقل إلى إحدى جاراتها
ثم ينتقل إلى أحدى جارات الـ Node الذي اختاره ثم ينتقل إلى أحدى جاراتها وهكذا حتى يصل إلى الـ Node المطلوب
فهو يبحث في العمق أولًا على عكس الـ BFS الذي كان ببحث بشكل عرضي أي أنه يبحث في الذي يحيط به أولًا
هنا الـ DFS يبحث في العمق أولًا ويظل يتعمق حتى يصل إلى الـ Node المطلوبة
أول يصل إلى طريق مسدود وحينها يبدأ في الرجوع للخلف ويبحث في الـ Node أخرى ويظل يبحث ويتعمق فيها وهكذا

فكرة الرجوع للخلف واتخاذ طريق آخر تسمى Backtracking وهي فكرة مهمة في الـ DFS
ويمكنك قراءة مقالة ما هي دالة الـ Recursion التي تستدعي نفسها لفهم هذه الفكرة بشكل أفضل

على أي حالة فكرة الـ Recursion تعتبر من أهم الأفكار في الـ DFS والتي يمكنك استخدامها لتطبيق الـ DFS
لكننا لن نستخدم الـ Recursion في الشرح بالسنستخدم Data Structure الـ Stack في هذه المقالة

لنأخذ مثالًا لفهم الـ DFS وهذا المثال سيكون نفس الجراف الذي استخدمناه في الـ BFS

              user_5      user_2      user_6
                |           |           |
                |           |           |
  user_9 ---- user_1 ---- user_0 ---- user_3 ---- user_10
                |           |           |
                |           |           |
              user_8      user_4      user_7

لنفترض أننا نقف عند الـ user_0 ونريد الوصول إلى الـ user_8 باستخدام الـ DFS

نبدأ من الـ user_0 وننظر إلى جيرانه user_1, user_2, user_3, user_4
هنا في الـ DFS سنختار أحد الجيران ونبدأ بالبحث فيه فورًا لذا سنختار أول جارة (حسب ترتيب معين مثل ترتيب الإدخال) وفي هذه الحالة نختار user_1
الآن نكرر العملية مع user_1 ننظر إلى جاراته user_0, user_5, user_8, user_9 نستثني user_0 لأنه تم زيارته سابقًا

هنا سنختار أحد الجيران وسيكون user_5 ونكرر العملية معه وهكذا حتى نصل إلى الـ user_8

هل تلاحظ الفرق بين الـ DFS والـ BFS ؟
الـ DFS يركز على أول Node يجده ويبدأ بالبحث فيه فورًا ويتعمق فيه دون الاهتمام أو معرفة بالـ Node الأخرى الذي تحيط به
أما الـ BFS يركز على الـ Node الذي تحيط به أولًا ويبدأ بالبحث فيهم

حسنًا لنبدأ بتحليل الخطوات الذي سيتبعها الـ DFS للوصول إلى الـ user_8

نبدأ من الـ user_0 ونسأل السؤال المعتاد هل هو الـ user_8 الذي نبحث عنه ؟
الاجابة لا لذا سنبدأ بالبحث في جيرانه وهم user_1, user_2, user_3, user_4
الـ DFS سيضع كل هؤلاء الأشخاص في الـ Stack ويبدأ بالبحث في فيهم
وبما أن الـ Stack يعمل بنظام LIFO أي أن آخر الذي يدخل هو الأول الذي يخرج
فسنفترض أن الـ DFS وضعهم في الـ Stack بالترتيب التالي user_4, user_3, user_2, user_1

Stack: [user_4, user_3, user_2, user_1]
Visted: [user_0]

هنا أخر Node دخلت الـ Stack هو الـ user_1 لذا سيبدأ البحث فيه
ويرى جيرانه وهم user_0, user_5, user_8, user_9 ويضعهم في الـ Stack ويبدأ بالبحث فيهم
لكنه سيستثني الـ user_0 لأنه تم زيارته سابقًا وموضوع في الـ visited كما في الـ BFS

Stack: [user_4, user_3, user_2, user_5, user_8, user_9]
Visted: [user_0, user_1]

هنا ما هي الـ Node التي عليها الدور ؟
ستجدها هي الـ user_9 لأنها آخر من دخل الـ Stack
لذا سيرى جيرانها وهم user_1 ولكنه تم زيارته سابقًا وموجود في الـ visited
لذا لن يضعه في الـ Stack
هكذا وصلنا إلى طريق مسدود هنا سينظر إلى الـ Stack ويبدأ بالبحث في الـ Node التي تم وضعها قبل الـ user_9 وهي الـ user_8
وهنا سيجد الـ user_8 وينهي البحث

هذا هو الـ DFS بشكل بسيط وسهل
وهو يعتبر من الخوارزميات الهامة في الجراف والتي يمكنك استخدامها في العديد من التطبيقات
ويمكنك تطبيقها بسهولة على الجراف الذي تريده والبحث فيه

تطبيق عملي للـ DFS

لنقم بكتابة دالة الـ DFS

function dfs(graph: LinkedList[], start: number, target: number): boolean {
  let stack: Stack = new Stack();
  let visited: boolean[] = Array.from(
    { length: graph.length },
    () => false
  );

  stack.push(start);
  visited[start] = true;

  while (stack.length > 0) {
    let current = stack.pop();

    if (current === target) {
      return true;
    }

    for (let node = graph[current].head; node != null; node = node.next) {
      if (!visited[node.value]) {
        stack.push(node.value);
        visited[node.value] = true;
      }
    }
  }

  return false;
}

هل تلاحظ أن الدالة تشبه الـ BFS ؟
الدالة هي نفس الدالة تماما دون فرق، والاختلاف الوحيد أننا استخدمنا الـ Stack بدلا من الـ Queue فقط
وهذا يعتبر الفرق الوحيد بين الـ DFS والـ BFS من ناحية كتابة الكود
لكن طريقة البحث تختلف تمامًا بين الـ DFS والـ BFS باختلاف الـ Data Structure المستخدمة

لنقم بتجربة الـ DFS

dfs(graph, 0, 8); // true

بالطبع يوجد شكل آخر للـ DFS وهو استخدام الـ Recursion وهو الشكل الأكثر استخدامًا للـ DFS
لأنه يعطي سلاسة ويطبق مفهوم الـ Backtracking بشكل أفضل

على أي حال لم اقوم بشرح الدالة بل أعتقد أنك تستطيع فهمها بنفسك
لذا قم برسم جراف عشوائي واستخدم ورقة وقلم وحاول تطبيق كلا الـ BFS والـ DFS عليه وحاول تتبعه وفهمه

الختام

هذه المقالة طويلة بعض الشيء ولكنها تحتوي على معلومات هامة ومفيدة
ولكن عليك أن تعرف أن هذه مجرد مقدمة للجراف والخوارزميات المتعلقة به
ويوجد خوارزمات وأمور وتفاصيل يصعب شرحها في مقالة واحدة
لذا اكتفيت بمقدمة بسيطة ومثالين عمليين للـ BFS والـ DFS
حتى مثالين بسيطين ليس إلا

لأنك فيما بعد ستجد تطبيقات معقدمة لكن إن كان لديك فهم جيد لأساسيات الجراف وتستطيع تخيل كيفية البحث فيه
باستخدام الـ BFS والـ DFS فكل شيء سيكون سهلًا مع الوقت والتطبيق

يمكنك البحث عن خوارزميات أخرى مثل Dijkstra و A* و Bellman-Ford وغيرها من الخوارزميات المتقدمة
لكن عليك أن تبدأ بأساسيات الجراف أولًا وتفهم كيفية تمثيله وكيفية البحث فيه
لديك مقالة عن بناء وحل الـ Maze بخوارزميات DFS والـ BFS سنقوم فيها بتطبيق عملي على Maze باستخدام الـ DFS والـ BFS

على أي حال أتمنى أن تكون قد استفدت من هذه المقالة وأن تكون قد فهمت الفكرة الأساسية للجراف والـ BFS والـ DFS
وأن تكون قد استمتعت بالقراءة والتطبيق
وأهم نصيحة لك أن يكون لديك ورقة وقلم وترسم الجراف وتطبق عليه الخوارزميات وتتبعها وتفهمها