المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › الرسوم البيانية 11 / 19 السابق التالي

تمارين

مراجعة المفاهيم

تمثيل الرسم البياني نفسه بطريقتين

لرسم بياني غير موجّه أربعة رؤوس A, B, C, D، وأضلاعه A-B, A-C, B-C, C-D.

  1. اكتب قائمة التجاور الخاصة به.
  2. املأ مصفوفة التجاور الخاصة به باستخدام 0 و1 فقط.
  3. لتحديد ما إذا كان A وD متصلين مباشرةً، أي تمثيل للرسم البياني يتطلب فحص مدخلة مخزّنة واحدة فقط؟
  4. إذا كان للرسم البياني رؤوس كثيرة لكن أضلاعه قليلة، فأي التمثيلين يستهلك عادةً مساحة أقل؟

الإجابة

  1. قائمة التجاور هي:

    A: B, C
B: A, C
C: A, B, D
D: C

  2. مصفوفة التجاور هي:

    A B C D
    A 0 1 1 0
    B 1 0 1 0
    C 1 1 0 1
    D 0 0 1 0

  3. في مصفوفة التجاور، يمكنك فحص الصف A والعمود D مباشرةً، مما يجعلها مناسبة تماماً لتحديد ما إذا كان أي رأسين متصلين مباشرةً.

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

ترتيبا الاجتياز بالعرض أولاً والاجتياز بالعمق أولاً

لرسم بياني غير موجّه رؤوس A, B, C, D, E وأضلاع A-B, A-C, B-D, C-D, D-E.

ابدأ من A. وكلما وُجدت عدة رؤوس مجاورة غير مزارة، فاخترها بالترتيب الأبجدي:

  1. اكتب ترتيب الزيارة في الاجتياز بالعرض أولاً (BFS).
  2. اكتب ترتيب الزيارة في الاجتياز بالعمق أولاً التعاودي (DFS).
  3. لماذا يجب أن يسجّل كلا الاجتيازين الرؤوس التي زُيرت بالفعل؟

الإجابة

  1. ترتيب الزيارة في BFS هو A, B, C, D, E. فهو يزور أولاً B وC الواقعين على مسافة ضلع واحد من A، ثم يزور D وE الأبعد مسافة.

  2. ترتيب الزيارة في DFS هو A, B, D, C, E. فهو يدخل مراراً في رأس مجاور غير مزار، متبعاً أولاً A → B → D → C. وعندما لا يجد C رأساً مجاوراً جديداً، يعود إلى D ثم يزور E.

  3. يحتوي الرسم البياني على دورة مثل A-B-D-C-A. فمن دون تسجيل الرؤوس المزارة، قد يزور الاجتياز الرؤوس نفسها مراراً حول الدورة ولا ينتهي انتهاءً طبيعياً.

هل يستطيع اجتياز واحد بالعرض أولاً زيارة الرسم البياني كاملاً؟

لرسم بياني غير موجّه رؤوس A, B, C, D, E, F، وله الأضلاع A-B, B-C, D-E فقط.

  1. أي الرؤوس يستطيع اجتياز واحد بالعرض أولاً بدءاً من A أن يزورها؟
  2. بناءً على السؤال 1، هل زار هذا الاجتياز كل رأس في الرسم البياني؟ ولماذا؟
  3. لنفترض أنك تفحص جميع الرؤوس بالترتيب الأبجدي وتبدأ اجتيازاً جديداً بالعرض أولاً كلما وصلت إلى رأس غير مزار. فما رأس البداية لكل اجتياز؟ وإلى كم جزء منفصل عن الآخر (مكوّن متصل) ينقسم الرسم البياني؟

الإجابة

  1. بدءاً من A، لا يستطيع الاجتياز زيارة سوى A, B, C.

  2. لم يزر كل الرؤوس. فـD, E يشكّلان جزءاً متصلاً آخر، بينما F رأس معزول. ولا يوجد لأي منها مسار إلى A، لذا لا يمكن الوصول إليها من A.

  3. تبدأ الاجتيازات الثلاثة بالعرض أولاً من A, D, F، وتزور {A, B, C} و{D, E} و{F} على الترتيب. لذلك يحتوي الرسم البياني على 3 مكوّنات متصلة.

تمارين برمجية

تحديد وجود مسار في رسم بياني غير موجّه

بمعطى رسم بياني غير موجّه فيه nn من الرؤوس مرقّمة من 00 إلى n−1n-1. وكل مدخلة [u, v] في المصفوفة edges تمثّل ضلعاً غير موجّه بين الرأسين u وv.

بمعطى أيضاً رأس بداية source ورأس وجهة destination. ابنِ أولاً قائمة تجاور من edges، ثم استخدم BFS أو DFS لتحديد ما إذا كان يوجد مسار من source إلى destination. وأعِد true إن وُجد مسار، وإلا فأعِد false. وقد يحتوي الرسم البياني على دورات وقد يكون غير متصل.

تلميحات

  1. أضف كل ضلع غير موجّه في الاتجاهين
  2. قد يحتوي الرسم البياني على دورات، لذا يجب تسجيل الرؤوس التي زُيرت بالفعل
  3. بدءاً من source، أعِد true إذا صادفت destination؛ وإذا انتهى الاجتياز دون الوصول إليه، فأعِد false

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي البحث