أشجار الامتداد الدنيا
في عام 1926، طُلب من أوتاكار بوروفكا (Otakar Borůvka) أن يخطط شبكة الكهرباء في جنوب مورافيا بأقل تكلفة ممكنة. سؤاله، أي كيف يُربط كل مكان بأقل طول كلي من الخطوط، هو مسألة شجرة الامتداد الدنيا، ولها بعض من أبسط الحلول وأكثرها أناقة في علوم الحاسوب كلها.
المسألة
خذ رسمًا بيانيًا متصلًا لحوافه أطوال، أو تكاليف. شجرة الامتداد هي مجموعة حواف تربط كل العقد ولا تحتوي على دورة؛ ومع n عقدة يكون لها دائمًا n − 1 حافة بالضبط، لأن كل حافة تصل عقدة إضافية. ومن بين كل أشجار الامتداد، تملك شجرة الامتداد الدنيا أصغر طول كلي. قد يكون للرسم البياني عدد هائل من أشجار الامتداد، لكن لا حاجة إلى تجربتها كلها.
لماذا تنجح الطريقة الجشعة
قسّم العقد إلى مجموعتين بأي طريقة. أقصر حافة تعبر بين المجموعتين تنتمي دائمًا إلى شجرة امتداد دنيا ما: فلو استخدمت شجرة بدلًا منها حافة عابرة أطول، لكان استبدالها بالأقصر يربط العقد نفسها بتكلفة أقل. هذه هي خاصية القطع. والوجه الآخر للعملة هو خاصية الدورة: أطول حافة في أي دورة لا تلزم أبدًا. والخوارزميتان أدناه تواصلان تطبيق هذه القواعد فحسب.
مثال
خذ الحواف A–B بطول 1، وB–C بطول 2، وA–C بطول 3، وC–D بطول 4، وB–D بطول 5. تأخذ خوارزمية كروسكال A–B، ثم B–C، ثم تتخطى A–C لأن A وC متصلتان بالفعل وستُغلق دورة، ثم تأخذ C–D. للشجرة ثلاث حواف لأربع عقد، فقد اكتملت، بطول كلي 7، ولم يُنظر إلى B–D أصلًا. أما خوارزمية بريم من A فتضيف أولًا B عبر A–B؛ وحافة B، أي B–C (2)، تتفوق على A–C (3) طريقًا إلى C، فتنضم C عبر B–C؛ وحافة C، أي C–D (4)، تتفوق على B–D (5)، فتنضم D عبر C–D. الشجرة نفسها، والمجموع نفسه: 7.
كروسكال وبريم وبوروفكا
خوارزمية كروسكال، التي نشرها جوزيف كروسكال (Joseph Kruskal) عام 1956، ترتّب الحواف وتستخدم بنية اتحاد-بحث لتتخطى الحواف داخل الجزء الواحد، فيزداد عملها بنسبة E log E. أما خوارزمية بريم فقد وصفها فويتيخ يارنيك (Vojtěch Jarník) أول مرة عام 1930، ثم أعاد اكتشافها روبرت بريم (Robert Prim) عام 1957 وإدسخر ديكسترا (Edsger Dijkstra) عام 1959؛ ومع كومة ثنائية يزداد عملها بنسبة E log V، ومع مصفوفة بسيطة بنسبة V²، وهذا جيد للرسوم البيانية الكثيفة. وخوارزمية بوروفكا من عام 1926 تجعل كل جزء يلتقط أقصر حافة خارجة منه في الوقت نفسه، وهو ما يناسب الحواسيب المتوازية.
الاستخدامات
تُستخدم أشجار الامتداد الدنيا لتصميم شبكات رخيصة من الكابلات والأنابيب والطرق. وهي تجمع البيانات في عناقيد: احذف أطول حواف الشجرة، فتكون الأجزاء المتبقية هي العناقيد. وتعطي جولة سريعة لمسألة البائع المتجول لا يزيد طولها عن ضعف أفضل جولة عندما تخضع المسافات لمتباينة المثلث. كما أن تشغيل خوارزمية كروسكال أو بريم على شبكة بأطوال حواف عشوائية طريقة كلاسيكية لتوليد متاهة.
استكشفها
افتح التطبيق، واختر كروسكال أو بريم، واضغط «خطوة». مع كروسكال، تُعرض الحواف التي لم تُجرَّب بعد أسفل الرسم البياني من الأقصر إلى الأطول؛ وتُرسم الحواف التي ستُغلق دورة بخط أحمر متقطع. ومع بريم، تُعرض العقد التي تنتظر الانضمام مع طول أفضل حافة لكل منها، وتُرسم تلك الحافة بخط متقطع. شغّل الاثنتين على الرسم البياني نفسه وقارن: الترتيب مختلف، لكن الطول الكلي هو نفسه دائمًا.
الأسئلة المتداولة
كم حافة في شجرة الامتداد؟
أقل من عدد العقد بواحدة بالضبط. فعدد أقل من الحواف لا يمكنه ربط كل العقد، وحافة واحدة إضافية تُنشئ دائمًا دورة.
أيهما أسرع، كروسكال أم بريم؟
خوارزمية كروسكال، التي ترتّب الحواف، أبسط عادةً وسريعة على الرسوم البيانية المتفرقة قليلة الحواف. وخوارزمية بريم مع كومة تؤدي جيدًا على الرسوم البيانية الكثيفة، ومع مصفوفة عادية تحتاج إلى نحو V² خطوة مهما كان عدد الحواف.
ما بنية اتحاد-بحث؟
بنية بيانات تتتبع أي العقد في الجزء نفسه. تجيب عن «هل هاتان متصلتان؟» وتدمج جزأين في لحظة تقريبًا، وهذا بالضبط ما تحتاج إليه خوارزمية كروسكال لكل حافة.
هل تصلح شجرة الامتداد الدنيا للرسوم البيانية الموجّهة؟
ليس كما هي. في الرسوم البيانية ذات الحواف أحادية الاتجاه، المسألة المقابلة هي شجرة الامتداد الموجّهة الدنيا (arborescence)، وتُحل بخوارزمية Chu–Liu/Edmonds.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
ابنِ شجرة امتداد دنيا