الدرس الثالث (٢)
انظر إلى الشيفرة البرمجية في أعلى الصفحة: هذه دالة برمجية تبحث عن العقد المجاورة في المخطط. في الصندوق الأسفل، ترى المخرجات عندما نطبق هذه الدالة على القاموس الذي يخزن المخطط. مثلاً، إذا كان لديك العقدة a وتتصل بالعقدتين b وc، فإن الدالة تنتج أزواجاً مثل ('a', 'b') و('a', 'c'). عندما نضيف أضلاعاً جديدة مثل إضافة الضلع بين c وf، ستلاحظ في مخرجات الصندوق الثاني أن الزوج ('c', 'f') قد ظهر في قائمة الأضلاع المحدثة للمخطط.
يركز هذا الدرس على هياكل البيانات غير الخطية وتحديداً المخططات وكيفية تمثيلها وبرمجتها باستخدام لغة بايثون. يعتمد الدرس على استخدام القواميس لتعريف العقد وربطها معا لتكوين شبكة متكاملة من البيانات. يتضمن الدرس تمارين وتطبيقات عملية مثل بناء برامج لمحاكاة الأنظمة وإدارة طوابير الانتظار. مثال سريع: عندما نعرف قاموسا يمثل مخططا مثل myGraph = {'a': ['b', 'c']}, فإننا نربط العقدة a بالعقدتين b وc لتكوين حواف المخطط.
الفكرة الأساسية
تدور الفكرة حول تمثيل البيانات في شكل غير خطي باستخدام هياكل معقدة كالمخططات وتطبيق ذلك برمجيا عبر لغة بايثون باستخدام القواميس لتخزين العلاقات بين العقد.
الشرح
انظر إلى طريقة بناء المخطط في لغة بايثون. نستخدم متغير نوعه قاموس لتمثيل المخطط، حيث يكون مفتاح القاموس هو العقدة الحالية، والقيمة هي قائمة العقد المجاورة المرتبطة بها. دالة مثل generate_edges تمر عبر كل عقدة في المخطط، ثم تفحص العقد المجاورة لها عبر حلقة تكرارية، وتضيف الحواف الناتجة إلى قائمة لتوضيح الروابط بين العقد. إذا أردنا إضافة حافة جديدة بين عقدتين، فنحن نستخدم دالة اضافة مثل addEdge لتحديث القاموس وإدراج العلاقة الجديدة بداخله.
مثال محلول خطوة بخطوة
لنفترض أن لديك المخطط التالي المعرف كقاموس في لغة بايثون: myGraph = {'a': ['b', 'c'], 'b': ['c', 'd'], 'c': [], 'd': []} الخطوة الأولى: استدعاء دالة توليد الحواف generate_edges(myGraph). الخطوة الثانية: تبدأ الدالة بفحص العقدة الأولى a وتجد أن لها جارين هما b وc، فتنشئ الحواف ('a', 'b') و('a', 'c'). الخطوة الثالثة: تنتقل الدالة للعقدة التالية b وتجد أن لها جارين هما c وd، فتنشئ الحواف ('b', 'c') و('b', 'd'). الخطوة الرابعة: تفحص العقدة c وd فلا تجد لهما جيرانا. الخطوة الخامسة: تعيد الدالة القائمة النهائية للحواف وتطبعها بالشكل التالي: [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'd')].
أخطاء شائعة
- كتابة اسم العقدة بخطأ إملائي داخل القاموس مما يؤدي إلى عدم مطابقتها عند البحث أو توليد الحواف.
- نسيان إضافة الأقواس المربعة عند تحديد قائمة العناصر المجاورة للعقدة.
سؤالان للتدريب مع الإجابة
السؤال الأول: كيف يمثل القاموس في لغة بايثون العلاقات بين العقد في المخطط؟ الإجابة: يكون مفتاح القاموس هو العقدة الأصل، وتكون القيمة عبارة عن قائمة تحتوي على العقد الفرعية أو المجاورة المرتبطة بها.
السؤال الثاني: ماذا تفعل الدالة عندما تمر على عقدة ليس لها عقد مجاورة؟ الإجابة: تترك قائمة العقد المجاورة فارغة داخل القاموس ولن تضيف أي حواف جديدة تخص هذه العقدة.