The Greedy Technique تقنية الـ Greedy (الجشع)

Optimization by taking the best immediate choice. "Take what you can get now, and hope for the best." التحسين (Optimization) عن طريق اتخاذ أفضل خيار فوري. "خذ ما يمكنك الحصول عليه الآن، وتأمل الأفضل."

Prim's Algorithm خوارزمية Prim Kruskal's Algorithm خوارزمية Kruskal Dijkstra's Algorithm خوارزمية Dijkstra Huffman Codes أكواد Huffman

The Greedy Philosophy فلسفة الـ Greedy

Constructs a solution piece by piece through a sequence of choices that follow three strict rules: تبني الحل قطعة بقطعة من خلال سلسلة من الخيارات التي تتبع ثلاث قواعد صارمة:

Feasible ممكن/مجد (Feasible)

Must satisfy problem constraints. يجب أن يلبي قيود المشكلة.

Locally Optimal أمثل محلياً (Locally Optimal)

Best immediate choice (e.g., cheapest edge). أفضل خيار فوري (مثل أرخص ضلع).

Irrevocable غير قابل للرجوع (Irrevocable)

Once made, the choice cannot be changed. بمجرد اتخاذ الخيار، لا يمكن تغييره.

Minimum Spanning Trees (MST) أشجار الامتداد الأصغرية (MST)

Connect all vertices with minimum total edge weight. No cycles allowed. $|E| = |V| - 1$. ربط جميع الرؤوس (Vertices) بأقل وزن إجمالي للأضلاع. غير مسموح بالحلقات (Cycles). المعادلة: $|E| = |V| - 1$.

Prim's Algorithm خوارزمية Prim

The "Mold" Strategy استراتيجية العفن (Mold Strategy)

Grow a single tree from a starting vertex. At each step, add the nearest vertex not yet in the tree. تنمية شجرة واحدة من رأس البداية. في كل خطوة، أضف أقرب رأس ليس في الشجرة بعد.

  • Data Structure: Priority Queue. هيكل البيانات: Priority Queue.
  • Complexity: $O(|E| \log |V|)$. التعقيد: $O(|E| \log |V|)$.

Kruskal's Algorithm خوارزمية Kruskal

The "Forest" Strategy استراتيجية الغابة (Forest Strategy)

Sort all edges by weight. Add the cheapest edge anywhere, provided it doesn't create a cycle (connects two disjoint trees). رتب جميع الأضلاع حسب الوزن. أضف أرخص ضلع في أي مكان، بشرط ألا ينشئ حلقة (يربط بين شجرتين منفصلتين).

  • Data Structure: Union-Find. هيكل البيانات: Union-Find.
  • Complexity: $O(|E| \log |E|)$. التعقيد: $O(|E| \log |E|)$.

Dijkstra's Algorithm خوارزمية Dijkstra

Single-Source Shortest Path أقصر مسار من مصدر واحد

Finds the shortest path from a Source vertex to ALL other vertices. It is structurally almost identical to Prim's Algorithm, but the "Priority" label differs. تجد أقصر مسار من رأس المصدر (Source) إلى جميع الرؤوس الأخرى. هي متطابقة هيكلياً تقريباً مع خوارزمية Prim، لكن تصنيف "الأولوية" يختلف.

Prim's Priority أولوية Prim $w(u, v)$

Distance from tree to vertex. المسافة من الشجرة إلى الرأس.

Dijkstra's Priority أولوية Dijkstra $d_u + w(u, v)$

Total distance from Source. إجمالي المسافة من المصدر.

Huffman Trees & Codes أشجار وأكواد Huffman

Data Compression ضغط البيانات (Data Compression)

Prefix-Free Code كود خالي من البادئة (Prefix-Free)

Assigns shorter binary codes to frequent characters and longer codes to rare characters. يخصص أكواد ثنائية أقصر للأحرف المتكررة وأكواد أطول للأحرف النادرة.

1

Initialize $n$ one-node trees with frequencies. تهيئة $n$ أشجار ذات عقدة واحدة مع الترددات.

2

Repeat $n-1$ times: Merge the two trees with smallest weights. كرر $n-1$ مرة: ادمج الشجرتين ذواتي أصغر أوزان.

3

Label left edges '0' and right edges '1'. قم بتسمية الحواف اليسرى '0' والحواف اليمنى '1'.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: The Change-Making Fallacy فخ: مغالطة صرف العملات (Change-Making)

"Does Greedy always work for Change Making?"
NO. It works for standard coins (1, 5, 10, 25). But for denominations like $\{1, 3, 4\}$ and target $6$, Greedy gives $4+1+1$ (3 coins), while optimal is $3+3$ (2 coins). "هل تعمل الـ Greedy دائماً مع صرف العملات؟"
لا. تعمل مع العملات القياسية. لكن مع فئات مثل $\{1, 3, 4\}$ وهدف $6$، تعطي Greedy النتيجة $4+1+1$ (3 عملات)، بينما الحل الأمثل هو $3+3$ (عملتان).

TRAP: Dijkstra & Negative Weights فخ: Dijkstra والأوزان السالبة

Dijkstra's Algorithm FAILS if the graph has negative edge weights. Once a vertex is "visited" (finalized), Dijkstra assumes its distance cannot get shorter. A negative edge later could violate this. Use Bellman-Ford instead. خوارزمية Dijkstra تفشل إذا كان الرسم البياني يحتوي على أوزان سالبة. بمجرد "زيارة" الرأس (تثبيته)، تفترض Dijkstra أن مسافته لا يمكن أن تقصر. وجود ضلع سالب لاحقاً قد ينتهك هذا. استخدم Bellman-Ford بدلاً منها.

SECRET: Prim vs Kruskal سر: Prim مقابل Kruskal

When to use which?
Dense Graphs ($|E| \approx |V|^2$): Use Prim's (with Matrix).
Sparse Graphs ($|E| \approx |V|$): Use Kruskal's (it depends on $|E|$). متى تستخدم أياً منهما؟
الرسوم الكثيفة ($|E| \approx |V|^2$): استخدم Prim (مع مصفوفة).
الرسوم المتناثرة ($|E| \approx |V|$): استخدم Kruskal (تعتمد على $|E|$).

KEY CONCEPT: Prefix-Free مفهوم مفتاحي: خالية من البادئة (Prefix-Free)

In Huffman coding, no code is a prefix of another (e.g., if 'A' is 01, 'B' cannot be 011). This property ensures we can decode the stream without ambiguity and without "separator" markers. في ترميز Huffman، لا يوجد كود هو بادئة لآخر (مثلاً، إذا كان 'A' هو 01، لا يمكن أن يكون 'B' هو 011). تضمن هذه الخاصية إمكانية فك تشفير البيانات دون غموض وبدون فواصل.