الدرس 14: الرسوم البيانية — BFS و DFS
فكّر في خريطة مدن متصلة بالطرق، أو أصدقاء على شبكة اجتماعية. أي شيء يمثّل 'نقاطاً وعلاقات بينها' هو 'رسم بياني' (graph): عُقَد (nodes) متصلة بحواف (edges). هناك طريقتان للتجول في الرسم البياني: BFS ينتشر حلقةً حلقةً مثل تموّج في الماء — ممتاز للمسار الأقصر؛ وDFS يغوص عميقاً مثل استكشاف متاهة، ويتراج
BFS مثل تموّج في الماء: تبدأ من نقطة واحدة وتنتشر حلقةً حلقةً نحو الخارج، الأقرب أولاً. DFS مثل السير في متاهة — تمضي حتى النهاية في مسار واحد، وإن تعثّرت تتراجع وتجرّب مساراً آخر.
- اجتياز الرسم البياني
- زيارة منهجية لكل عقدة يمكن الوصول إليها من عقدة البداية، باستخدام BFS (طابور) أو DFS (مكدّس/استدعاء ذاتي).
- قاموس الجوار
- تمثيل للرسم البياني حيث تُربَط كل عقدة بقائمة جيرانها: {node: [neighbors]} — وصول إلى الجيران بزمن O(1).
- مجموعة الزيارة
- مجموعة (set) تُعلّم أيّ العُقَد جرى مسحها بالفعل، لتجنّب زيارتها مرة أخرى ومنع الحلقات اللانهائية.
