- الحالية
- في الشجرة
- مجاورة للشجرة
- أفضل حافة حتى الآن
- ستُغلق دورة
شجرة الامتداد الدنيا
تريد أن تربط كل بلدة بالكابلات، أو كل منزل بأنابيب المياه، أو كل حاسوب في شبكة، بأقل قدر ممكن من المواد. الجواب هو شجرة الامتداد الدنيا: مجموعة الحواف التي تربط كل العقد بأقل طول كلي. اختر خوارزمية كروسكال أو بريم وتقدّم خطوة بخطوة لترى الشجرة تنمو، بأقصر حافة مسموحة في كل مرة. اضغط «تشغيل» لمشاهدة نمو الشجرة، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. اختر الخوارزمية: كروسكال تجرّب الحواف من الأقصر إلى الأطول، وبريم تنمّي شجرة واحدة من البداية؛ انقر على عقدة لتجعلها بداية بريم. الرقم على كل حافة هو طولها. أسفل الرسم البياني قائمة الحواف التي لم تُجرَّب بعد، أو العقد التي تنتظر الانضمام مع طول أفضل حافة لها إلى الشجرة. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- اختر خوارزمية كروسكال أو بريم. مع بريم، انقر على عقدة لتجعلها البداية.
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
- راقب الحواف وهي تنضم إلى الشجرة والطول الكلي وهو يزداد. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.
خوارزمية كروسكال
رتّب كل الحواف من الأقصر إلى الأطول وجرّبها بهذا الترتيب. إذا ربطت حافة جزأين غير متصلين بعد، تدخل الشجرة. وإذا كان طرفاها متصلين بالفعل عبر الشجرة، فإنها ستُغلق دورة، لذا تُتخطّى. توقّف عندما يصبح عدد حواف الشجرة أقل من عدد العقد بواحدة. ولمعرفة ما إذا كانت عقدتان متصلتين بالفعل بسرعة، تحفظ خوارزمية كروسكال الأجزاء في بنية اتحاد-بحث.
خوارزمية بريم
ابدأ بشجرة من عقدة واحدة. كل عقدة خارج الشجرة تتذكر أقصر حافة لها إلى الشجرة. أضف مرارًا العقدة ذات الحافة الأقصر، مع تلك الحافة، ثم افحص حوافها: قد تمنح إحداها جارًا طريقًا أقصر إلى الشجرة. تشبه خوارزمية بريم خوارزمية ديكسترا، لكنها تقارن حوافًا منفردة، لا مسافات كاملة من البداية. وتنتهي الخوارزميتان دائمًا بالطول الكلي نفسه.
الأسئلة المتداولة
ما شجرة الامتداد الدنيا؟
في رسم بياني متصل لحوافه أطوال، شجرة الامتداد هي مجموعة حواف تربط كل العقد دون أي دورة؛ ومع n عقدة يكون لها دائمًا n − 1 حافة. وشجرة الامتداد الدنيا هي شجرة امتداد طولها الكلي أصغر ما يمكن.
ما الفرق بين خوارزميتي كروسكال وبريم؟
تنظر خوارزمية كروسكال إلى حواف الرسم البياني كله من الأقصر إلى الأطول، وتضم الأجزاء المنفصلة في شجرة واحدة. أما خوارزمية بريم فتنمّي شجرة واحدة من البداية، مضيفةً دائمًا أقصر حافة خارجة منها. كلتاهما جشعة وتجدان شجرة بالطول الكلي نفسه؛ كروسكال تناسب الرسوم البيانية المتفرقة، وبريم تناسب الكثيفة.
هل شجرة الامتداد الدنيا فريدة؟
نعم، عندما تكون أطوال الحواف كلها مختلفة. وعندما تتساوى بعض الأطوال، قد توجد عدة أشجار بأصغر مجموع نفسه، وقد تختار الخوارزميات أشجارًا مختلفة بحسب طريقة فضّها للتعادل.
هل شجرة الامتداد الدنيا هي نفسها أقصر المسارات؟
لا. تُبقي شجرة الامتداد الدنيا الطول الكلي لكل الحواف صغيرًا، لكن المسار بين عقدتين في الشجرة قد يكون أطول بكثير من أقصر مسار بينهما. لأقصر المسارات، استخدم خوارزمية ديكسترا.
هل يُرسل الرسم البياني إلى أي مكان؟
لا. يُنشأ الرسم البياني وتُبنى الشجرة داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر