37. تمثيل الرسوم البيانية

تؤثر كيفية تخزين بيانات الرسم البياني بشكل كبير على كفاءة الخوارزميات التي تعمل عليها.

1. مصفوفة التجاور (Adjacency Matrix)

• المفهوم: مصفوفة ثنائية الأبعاد (V x V)، حيث V هو عدد الرؤوس.
• التخزين: تخزن Matrix[i][j] قيمة 1 (أو الوزن) إذا كانت هناك حافة من الرأس i إلى الرأس j، و 0 (أو ما لا نهاية) بخلاف ذلك.
• الإيجابيات: التحقق السريع من وجود حافة بين عُقدتين محددتين (O(1)).
• السلبيات: تُهدر الكثير من المساحة، خاصة بالنسبة لـ الرسوم البيانية القليلة (Sparse Graphs) (الرسوم البيانية ذات الحواف القليلة). التعقيد المكاني: O(V²).

2. قائمة التجاور (Adjacency List)

• المفهوم: مصفوفة أو Hash Map حيث يتوافق كل فهرس/مفتاح مع رأس. القيمة المخزنة في ذلك الفهرس هي قائمة جيرانه.
• الإيجابيات: كفاءة في المساحة، خاصة للرسوم البيانية القليلة. التعقيد المكاني: O(V + E) (الرؤوس + الحواف).
• السلبيات: يتطلب التحقق مما إذا كانت هناك حافة موجودة بين عُقدتين البحث في قائمة الجيران (O(درجة الرأس)).

قاعدة عامة: تُفضل قوائم التجاور عادةً لمعظم خوارزميات العالم الحقيقي ما لم يكن الرسم البياني كثيفاً للغاية.