قائمة المجاورة وتمثيل مصفوفة الرسم البياني
فريق التحرير
⚡ ملخص ذكي
تُخزّن قوائم التجاور ومصفوفات تمثيل الرسم البياني الرؤوس والحواف في الذاكرة، مما يسمح للخوارزميات باجتياز الشبكات. تستخدم قوائم التجاور قوائم مرتبطة لكل رأس، بينما تستخدم مصفوفات التجاور شبكة مربعة ثنائية الأبعاد.
على الرغم من أنها تبدو مختلفة، كل شيء أنواع الرسوم البيانية يمكن تمثيلها بطريقة مماثلة. يوجد عمومًا نوعان من تمثيل الرسوم البيانية:
- مصفوفة الجوار
- قائمة الجوار
قائمة الجوار
تتكون قائمة التجاور من قوائم متصلة. يُعتبر كل رأس فهرسًا في المصفوفة، ويمثل كل عنصر قائمة متصلة. تحتوي هذه القوائم المتصلة على الرؤوس التي تشترك في حافة مع رأس الفهرس.
فيما يلي مثال على قائمة مجاورة:
لنفترض أن الرسم البياني يحتوي على V من الرؤوس و E من الحواف. التعقيد المكاني لقائمة التجاور هو O(V + E)، والذي يتناسب مع عدد الحواف الحقيقية بدلاً من كل زوج ممكن من الرؤوس.
يصبح تعقيد المساحة في أسوأ الحالات O(V²) إذا كان الرسم البياني المعطى رسمًا بيانيًا كاملاً، لأن كل رأس يتصل بكل رأس آخر.
مصفوفة الجوار
تتكون مصفوفة التجاور من مصفوفة ثنائية الأبعاد. بالنسبة لرسم بياني يحتوي على V رأسًا، سيكون حجم المصفوفة V × V.
قل matrix[i][j] = 5وهذا يعني وجود حافة بين العقدة i والعقدة j حيث يكون الوزن 5.
لنلقِ نظرة على الرسم البياني التالي ومصفوفة التجاور الخاصة به:
بنينا مجموعة 2D باستخدام هذه الخطوات:
الخطوة 1) للرأس A حافة مباشرة مع B، ووزنها 5. لذلك، سيتم ملء الخلية في الصف A والعمود B بالقيمة 5. أما بقية الخلايا في الصف A فسيتم ملؤها بالصفر.
الخطوة 2) للرأس B حافة مباشرة مع C، ووزنها 4. لذلك، سيتم ملء الخلية في الصف B والعمود C بالقيمة 4. أما الخلايا المتبقية في الصف B فسيتم ملؤها بالقيمة صفر، لأن B ليس له حافة صادرة إلى أي عقدة أخرى.
الخطوة 3) لا توجد حواف مباشرة بين الرأس C وأي رأس آخر. لذا، سيتم ملء الصف C بالأصفار.
الخطوة 4) للرأس D حافة موجهة مع A و C.
- ستكون قيمة الخلية في الصف D والعمود A هي 7. وستكون قيمة الخلية في الصف D والعمود C هي 2.
- سيتم ملء بقية الخلايا في الصف D بالأصفار.
الخطوة 5) للرأس E حافة موجهة مع B و D. ستكون قيمة الخلية في الصف E والعمود B هي 6. ستكون قيمة الخلية في الصف E والعمود D هي 3. أما بقية الخلايا في الصف E فستكون مملوءة بأصفار.
فيما يلي بعض النقاط التي يجب ملاحظتها:
- لا يحتوي الرسم البياني على حلقات ذاتية عندما يكون القطر الرئيسي لمصفوفة التجاور 0.
- يكون الرسم البياني موجهاً إذا لم تكن قيم الخلايا عند النقطتين (أ، ب) و(ب، أ) متطابقة. وإلا، يكون الرسم البياني غير موجه.
- يكون الرسم البياني رسماً بيانياً مرجحاً إذا كانت قيمة أي خلية أكبر من 1.
تكمن المشكلة الرئيسية في مصفوفة التجاور في أنها تتطلب مساحة مربعة. حتى الحواف غير الموجودة تشغل خلايا في الذاكرة.
على سبيل المثال، إذا كان لدينا رسم بياني يحتوي على 100 عقدة، فسنحتاج إلى 10,000 خلية لتخزينه في راماتمع وجود عدد أقل من الحواف في الرسم البياني، قد يكون تخصيص ذاكرة كبيرة كهذه تبذيرًا. لذا فإن تعقيد المساحة باستخدام مصفوفة التجاور هو O(N²)، حيث N هو عدد العقد في الرسم البياني.
قائمة التجاور مقابل مصفوفة التجاور
قبل اختيار التمثيل، من المفيد مقارنة كلا النموذجين جنبًا إلى جنب عبر العمليات التي تهيمن على أحمال العمل الحقيقية للرسوم البيانية:
| تشغيل | مصفوفة الجوار | قائمة الجوار |
|---|---|---|
| تعقيد الفضاء | O(V²) | O(V + E) |
| أضف رأسًا | O(V²) | يا (1) |
| أضف لمسة مميزة | يا (1) | يا (1) |
| إزالة حافة | يا (1) | يا (ه) |
| تحقق مما إذا كانت الحافة (i, j) موجودة | يا (1) | O(درجة i) |
| قم بالتكرار على جيران i | يا (الخامس) | O(درجة i) |
| أفضل ل | الرسوم البيانية الكثيفة، والاستعلامات المتكررة على الحواف | الرسوم البيانية المتفرقة، والمهام التي تتطلب اجتيازًا مكثفًا |
باختصار، تتفوق مصفوفة التجاور في عمليات البحث عن الحواف في الوقت الثابت، بينما تتفوق قائمة التجاور في الذاكرة وتكرار الجوار، ولهذا السبب عادةً ما تقترن خوارزميات مثل BFS وDFS وDijkstra بقوائم التجاور.
مزايا وعيوب تمثيل الرسوم البيانية
لكل نموذج مزاياه وعيوبه. معرفة نقاط القوة والضعف في كلا النموذجين تساعدك على اختيار النموذج الأنسب للمشكلة التي تحاول حلها.
مزايا مصفوفة التجاور:
- استعلامات عن وجود الحواف في وقت ثابت O(1) بين أي زوج من الرؤوس.
- إن الفهرسة الثابتة تجعل الخوارزميات القائمة على المصفوفات مثل فلويد-وارشال والإغلاق المتعدي سهلة التنفيذ.
- تتناسب الحواف الموزونة بشكل طبيعي في خلية مصفوفة واحدة.
عيوب مصفوفة التجاور:
- يهدر O(V²) من الذاكرة عندما يكون الرسم البياني متفرقًا.
- إضافة رأس جديد تتطلب تغيير حجم المصفوفة بأكملها.
- يستغرق التكرار على جيران رأس واحد O(V) حتى عندما يكون للرأس عدد قليل من الحواف.
مزايا قائمة التجاور:
- يستخدم فقط O(V + E) من الذاكرة، وهو قريب من عدد الحواف الحقيقي في الرسوم البيانية المتفرقة.
- إضافة رأس أو حافة جديدة هي O(1).
- تقوم خوارزميات الاجتياز مثل BFS و DFS بتكرار الجيران في O(degree)، مما يعطي وقت تشغيل إجمالي قدره O(V + E).
عيوب قائمة التجاور:
- يستغرق التحقق مما إذا كانت حافة معينة موجودة وقت O(degree) بدلاً من O(1).
- تكون خاصية التوطين في ذاكرة التخزين المؤقت أضعف لأن القوائم المرتبطة متناثرة عبر الذاكرة.
- تحتاج الحواف الموزونة إلى حقل مصاحب أو قائمة من الأزواج، مما يزيد من تعقيد بنية البيانات قليلاً.
متى نستخدم قائمة التجاور مقابل مصفوفة التجاور
يعتمد اختيار التمثيل على كثافة الرسم البياني والعمليات التي تُجريها بشكل متكرر. استخدم هذا الدليل السريع لاختيار البنية المناسبة:
- يفضل استخدام مصفوفة التجاور عندما يكون الرسم البياني كثيفًا (E قريب من V²)، وعندما تتغير الحواف نادرًا، وعندما تسأل خوارزميتك "هل هناك حافة بين i و j؟" عدة مرات.
- يفضل استخدام قائمة الجوار عندما يكون الرسم البياني متفرقًا (E أصغر بكثير من V²)، وعندما تنمو مجموعة الرؤوس أو الحواف أثناء التنفيذ، وعندما تجتاز الرسم البياني باستخدام BFS أو DFS أو خوارزمية ديكسترا لأقصر مسار.
- أفضل نموذجًا مختلطًا (قائمة الجوار بالإضافة إلى مجموعة تجزئة من الحواف) عندما تحتاج إلى كل من التكرار السريع للجيران والاستعلامات عن الحواف O(1)، على حساب الذاكرة الإضافية.
تعتمد مكتبات الرسوم البيانية الحديثة مثل NetworkX و igraph بشكل افتراضي على قوائم التجاور لأن معظم الرسوم البيانية في العالم الحقيقي - الشبكات الاجتماعية، وخرائط الطرق، وصفحات الويب، وتبعيات الحزم - تكون متفرقة وتتطلب الكثير من عمليات الاجتياز.
