قائمة الجوار

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

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

• تستخدم إحدى طرق التنفيذ التي اقترحها غيدو فان روسوم جدول تجزئة لربط كل رأس في الرسم البياني بمصفوفة من الرؤوس المجاورة. في هذا التمثيل، يمكن تمثيل الرأس بأي كائن قابل للتجزئة. لا يوجد تمثيل صريح للحواف ككائنات. ^{[ 1 ]}
• يقترح كورمن وآخرون تطبيقًا تُمثَّل فيه الرؤوس بأرقام فهرسية. ^{[ 2 ]} يستخدم تمثيلهم مصفوفة مفهرسة برقم الرأس، حيث تشير خلية المصفوفة لكل رأس إلى قائمة مرتبطة أحادية الاتجاه للرؤوس المجاورة لذلك الرأس. في هذا التمثيل، يمكن تفسير عُقد القائمة المرتبطة أحادية الاتجاه ككائنات حواف؛ ومع ذلك، فهي لا تخزن المعلومات الكاملة عن كل حافة (فهي تخزن فقط إحدى نقطتي نهاية الحافة)، وفي الرسوم البيانية غير الموجهة، سيكون هناك عقدتان مختلفتان في القائمة المرتبطة لكل حافة (واحدة ضمن القوائم لكل من نقطتي نهاية الحافة).
• تتضمن بنية قائمة التواجد الكائنية التوجه، التي اقترحها جودريتش وتاماسيا، فئات خاصة من كائنات الرؤوس وكائنات الحواف. يحتوي كل كائن رأس على متغير يشير إلى كائن مجموعة يسرد كائنات الحواف المجاورة. بدوره، يشير كل كائن حافة إلى كائني الرأس عند طرفيه. ^{[ 3 ]} يستهلك هذا الإصدار من قائمة التجاور ذاكرة أكبر من الإصدار الذي تُسرد فيه الرؤوس المتجاورة مباشرةً، لكن وجود كائنات حواف صريحة يمنحه مرونة إضافية في تخزين معلومات إضافية حول الحواف.

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

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

البديل الرئيسي لقائمة التجاور هو مصفوفة التجاور ، وهي مصفوفة تُفهرس صفوفها وأعمدتها برؤوسها، وتحتوي خلاياها على قيمة منطقية تُشير إلى وجود حافة بين الرأسين المُقابلين للصف والعمود في الخلية. بالنسبة للرسوم البيانية المتفرقة (التي لا ترتبط فيها معظم أزواج الرؤوس بحواف)، تُعد قائمة التجاور أكثر كفاءة في استخدام المساحة من مصفوفة التجاور (المخزنة كمصفوفة ثنائية الأبعاد): يتناسب استخدام المساحة لقائمة التجاور مع عدد الحواف والرؤوس في الرسم البياني، بينما يتناسب استخدام المساحة لمصفوفة التجاور المخزنة بهذه الطريقة مع مربع عدد الرؤوس. مع ذلك، يُمكن تخزين مصفوفات التجاور بكفاءة أكبر في استخدام المساحة، بحيث تُطابق الاستخدام الخطي للمساحة لقائمة التجاور، وذلك باستخدام جدول تجزئة مُفهرس بأزواج الرؤوس بدلاً من المصفوفة.

يتمثل الاختلاف الجوهري الآخر بين قوائم التجاور ومصفوفات التجاور في كفاءة العمليات التي تُنفذها. ففي قائمة التجاور، يُمكن سرد جيران كل رأس بكفاءة عالية، في زمن يتناسب مع درجة الرأس. أما في مصفوفة التجاور، فتستغرق هذه العملية زمنًا يتناسب مع عدد الرؤوس في الرسم البياني، والذي قد يكون أكبر بكثير من درجة الرأس. من ناحية أخرى، تسمح مصفوفة التجاور باختبار ما إذا كان رأسان متجاورين في زمن ثابت؛ بينما تُعد قائمة التجاور أبطأ في دعم هذه العملية.

يُعدّ مصفوفة التجاور البديل الرئيسي لقائمة التجاور عند استخدامها كبنية بيانات. ولأن كل عنصر في مصفوفة التجاور لا يتطلب سوى بت واحد، يمكن تمثيلها بطريقة مضغوطة للغاية، إذ تشغل فقط | V | ^² /⁸ بايت من المساحة المتجاورة، حيث | V | هو عدد رؤوس الرسم البياني. وإلى جانب تجنب المساحة المهدرة، يُعزز هذا الاختصار مبدأ المرجعية الموضعية .

مع ذلك، بالنسبة للرسوم البيانية المتفرقة، تتطلب قوائم التجاور مساحة أقل، لأنها لا تهدر أي مساحة لتمثيل الحواف غير الموجودة. باستخدام تطبيق مصفوفة بسيط على حاسوب 32 بت، تتطلب قائمة تجاور لرسم بياني غير موجه حوالي 2 × (32/8) | E | = 8 | E | بايت من المساحة، حيث | E | هو عدد حواف الرسم البياني.

بملاحظة أن الرسم البياني البسيط غير الموجه يمكن أن يحتوي على عدد أقصى من الحواف ^يساوي ( | V | ^² - | V | )/2 ≈ V² ، مع السماح بوجود الحلقات، يمكننا أن نرمز بكثافة الرسم البياني بـ d = | E | / | V | ^² . عندئذٍ، يكون | E | > | V | ^² /8 عندما يكون | E | / | V | ^² > 1/64 ، أي أن تمثيل قائمة التجاور يشغل مساحة أكبر من تمثيل مصفوفة التجاور عندما يكون d > 1/64 . وبالتالي، يجب أن يكون الرسم البياني متفرقًا بدرجة كافية لتبرير استخدام تمثيل قائمة التجاور.

إلى جانب المفاضلة المتعلقة بالمساحة، تُسهّل هياكل البيانات المختلفة عملياتٍ متنوعة. فإيجاد جميع الرؤوس المجاورة لرأسٍ مُحدد في قائمة التجاور بسيطٌ كقراءة القائمة نفسها. أما باستخدام مصفوفة التجاور، فيجب مسح صفٍ كامل، وهو ما يستغرق زمنًا قدره O ( | V | ) . يُمكن تحديد وجود حافة بين رأسين مُحددين دفعةً واحدة باستخدام مصفوفة التجاور، بينما يتطلب الأمر زمنًا يتناسب مع الحد الأدنى لدرجة هذين الرأسين باستخدام قائمة التجاور.

• إبستين، ديفيد (1996). "ملاحظات محاضرة ICS 161: خوارزميات الرسوم البيانية" . مؤرشف من الأصل بتاريخ 2025-01-04.

• تُنفذ مكتبة Boost Graph قائمة مجاورة فعالة
• هياكل البيانات المفتوحة، القسم 12.2، قائمة التجاور: الرسم البياني كمجموعة من القوائم ، بات مورين