Graph Terminology
المكونات الأساسية
الرسم البياني $G = (V, E)$ يتكون من رؤوس (Vertices) وحواف (Edges) تربط بينها.
- Directed (Digraph): الحافة لها اتجاه (سهم).
- Weighted: الحافة لها تكلفة (Cost/Weight).
- Path: تسلسل من الرؤوس المتصلة.
- Cycle: مسار يبدأ وينتهي بنفس الرأس.
- Acyclic (DAG): رسم موجه بدون دورات (مهم للـ Topological Sort).
Topological Sort
ترتيب المهام (Prerequisites)
ترتيب خطي للرؤوس بحيث إذا كان هناك سهم من $u$ إلى $v$، فإن $u$ يظهر قبل $v$ في الترتيب.
- احسب عدد الأسهم الداخلة (Indegree) لكل رأس.
- ضع الرؤوس ذات الـ Indegree = 0 في طابور.
- بينما الطابور غير فارغ:
- احذف الرأس واطبعه.
- أنقص الـ Indegree لكل جيرانه.
- إذا أصبح Indegree لجار يساوي 0، أضفه للطابور.
Shortest Path Algorithms
Unweighted Graph (BFS)
إذا كانت الحواف بدون وزن (أو متساوية)، فإن أقصر مسار هو "أقل عدد من الحواف".
ابدأ من المصدر، زر الجيران (مسافة 1)، ثم جيران الجيران (مسافة 2)...
Weighted Graph (Dijkstra)
إذا كانت الحواف لها تكلفة، نستخدم Dijkstra (خوارزمية جشعة Greedy).
- اجعل مسافة الجميع $\infty$ والمصدر 0.
- اختر العقدة المجهولة ذات أقل مسافة (Smallest Unknown).
- حدث مسافات جيرانها (Relaxation).
- اعتبرها "معلومة" (Known). كرر.
Minimum Spanning Tree (MST)
ما هي شجرة الامتداد؟
هي شجرة تربط جميع رؤوس الرسم البياني بأقل تكلفة إجمالية للحواف، وبدون أي دورات (Cycles).
تشبه Dijkstra جداً.
نبدأ من أي عقدة، وفي كل خطوة نضيف أرخص حافة تربط "ما لدينا" بـ "عقدة جديدة".
Min Cost
No Cycles
Dijkstra & Negative Edges
خوارزمية Dijkstra لا تعمل إذا كان الرسم البياني يحتوي على حواف سالبة (Negative Edges).
السبب: الخوارزمية "جشعة" وتفترض أن المسافة لا يمكن أن تقل بعد إضافة حافة جديدة، والسالب يكسر هذه القاعدة.
Cycle Detection
الـ Topological Sort يعمل فقط على DAG (Directed Acyclic Graph).
إذا كان هناك دورة (Cycle)، لن نجد أي رأس بـ Indegree 0 في مرحلة ما، وستفشل الخوارزمية.