ما هو الـ Graph؟
الدرس 2 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
الـ graph (الرسم البياني) هو هيكل بيانات يمثل مجموعة من الأشياء و الروابط التي تجمع بينها. تسمى هذه الأشياء vertices (رؤوس أو عقد) وتسمى الروابط edges (حواف).
الرسوم البيانية موجودة في كل مكان. الشبكات الاجتماعية هي رسوم بيانية (الأشخاص هم vertices، والصداقات هي edges). خرائط الطرق هي رسوم بيانية (التقاطعات هي vertices، والشوارع هي edges). الإنترنت، وأشجار التبعية، وخرائط الألعاب كلها رسوم بيانية.
في هذه الدورة، سنركز على الرسم البياني undirected (غير الموجه): إذا كانت هناك حافة تربط بين u و v، فإن v متصل أيضاً بـ u. لا يوجد اتجاه محدد. سنستخدم integers (أعداداً صحيحة) كمفاتيح للرؤوس لتبسيط الأمور.
داخلياً، سنقوم بتخزين الرسم البياني كـ adjacency list (قائمة تجاور): وهي عبارة عن خريطة (map) تربط كل رأس بقائمة جيرانه. هذا يجعل عملية البحث عن جيران رأس معين تتم عبر وصول واحد للخريطة، وهو ما تحتاجه معظم خوارزميات الرسوم البيانية.
العمليات التي سنبنيها في فئة Graph هي:
- addVertex: إضافة رأس جديد بدون حواف بعد.
- addEdge: الربط بين رأسين.
- hasEdge: التحقق مما إذا كان هناك رابط بين رأسين.
- getNeighbors: الحصول على قائمة جيران رأس معين.
- removeEdge: قطع الاتصال بين رأسين.
- size: حساب عدد الرؤوس في الرسم البياني.
لنقم ببناء فئة Graph!
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.