ما هي الشجرة الممتدة الصغرى؟

هي مجموعة جزئية من حواف رسم بياني تربط كل عقدة ببعضها، ولا تحتوي على دورات، ولها أقل وزن إجمالي ممكن للحواف بين كل تلك المجموعات الجزئية الرابطة.

كيف تعمل خوارزمية كروسكال؟

ترتب كل الحواف حسب الوزن من الأصغر إلى الأكبر، ثم تعالجها بالترتيب، مضيفة كل حافة إلى الشجرة فقط إذا كانت تربط جزأين غير متصلين سابقًا من الرسم البياني (يُتحقق منه بكفاءة باستخدام بنية Union-Find).

ما فائدة Union-Find؟

يتتبع Union-Find (يُسمى أيضًا المجموعة المنفصلة) بكفاءة العقد المتصلة بالفعل، مما يتيح لخوارزمية كروسكال اكتشاف ما إذا كانت إضافة حافة ستُنشئ دورة بسرعة، دون إعادة مسح الشجرة بأكملها في كل مرة.

ماذا لو كان رسمي البياني غير متصل؟

تُبلغ الآلة الحاسبة بدلًا من ذلك عن غابة ممتدة صغرى — أرخص طريقة لربط كل مكون غير متصل داخليًا، لأنه لا يمكن لشجرة واحدة أن تمتد عبر عقد لا يوجد بينها مسار.

هل الشجرة الممتدة الصغرى فريدة دائمًا؟

ليس بالضرورة — إذا اشتركت عدة حواف في نفس الوزن، يمكن أن توجد أكثر من شجرة ممتدة صغرى صالحة بنفس الوزن الإجمالي، رغم أن الوزن الإجمالي نفسه دائمًا فريد.

كيف يختلف هذا عن خوارزمية ديكسترا؟

تُقلل الشجرة الممتدة الصغرى التكلفة الإجمالية لربط كل العقد معًا، بينما تُقلل خوارزمية ديكسترا تكلفة مسار بين عقدتين محددتين — يحل المسألتان أسئلة مختلفة رغم أن كلتيهما تعملان على رسوم بيانية موزونة.

كم عدد العقد التي يمكن أن تتعامل معها هذه الآلة الحاسبة؟

تدعم هذه الآلة الحاسبة حتى 50 عقدة، أكثر من كافٍ لأمثلة الرسوم البيانية المُدخلة يدويًا مع إبقاء حساب الترتيب وUnion-Find فوريًا.

أين تُستخدم الأشجار الممتدة الصغرى في الحياة الواقعية؟

تُستخدم لتصميم شبكات فعالة من حيث التكلفة — مد مسارات الكابلات أو الأنابيب، وتوصيل ألواح الدوائر، وتجميع نقاط البيانات، وتقريب حلول مشاكل تصميم الشبكات الأصعب.

آلة حاسبة الشجرة الممتدة الصغرى — أوجد أرخص طريقة لربط رسم بياني

تجد آلتنا الحاسبة للشجرة الممتدة الصغرى مجموعة الحواف التي تربط كل عقدة في رسم بياني موزون بأقل تكلفة إجمالية ممكنة، باستخدام خوارزمية كروسكال مع اكتشاف الدورات عبر Union-Find، مع إدخال رسمك البياني كقائمة حواف نصية بسيطة (مثل A-B:4, B-C:2).

إجابة سريعة

أدخل رسمك البياني الموزون كقائمة حواف لإيجاد الشجرة الممتدة الصغرى فورًا — أرخص مجموعة من الحواف تربط كل عقدة — عبر خوارزمية كروسكال.

الحواف (مفصولة بفواصل)

أدخل حوافًا موزونة بصيغة عقدةA-عقدةB:وزن، مثل A-B:4, B-C:2.

كيفية استخدام آلة حاسبة الشجرة الممتدة الصغرى — خوارزمية كروسكال عبر الإنترنت

1
أدخل رسمك البياني كقائمة حواف مفصولة بفواصل، مثل A-B:4, B-C:2.
2
انقر على 'احسب' لإيجاد الشجرة الممتدة الصغرى.
3
راجع الحواف المختارة والوزن الأدنى الإجمالي.

لماذا تستخدم آلة حاسبة الشجرة الممتدة الصغرى — خوارزمية كروسكال عبر الإنترنت؟

تربط الشجرة الممتدة الصغرى كل عقدة في رسم بياني باستخدام أقل عدد ممكن من الحواف الأرخص، دون دورات — بالضبط البنية التي تريدها عند تصميم شبكة (طرق، أنابيب، أسلاك دوائر) يجب أن تصل إلى كل نقطة بأقل تكلفة إجمالية. تجدها خوارزمية كروسكال بأناقة: رتّب كل الحواف من الأرخص إلى الأغلى، وأضف بجشع كل حافة لا تُنشئ دورة، متتبعة الاتصال بكفاءة باستخدام بنية بيانات Union-Find. هذا النهج الجشع مثبت أنه الأمثل، وتُشغّل هذه الآلة الحاسبة تلك الخوارزمية مباشرة على رسم بياني تُدخله كقائمة حواف موزونة.

الأسئلة الشائعة

أدوات ذات صلة

آلة حاسبة أقصر مسار لديكسترا — رسوم بيانية موزونة عبر الإنترنت

أوجد أقصر مسار والمسافة الإجمالية بين عقدتين في رسم بياني موزون باستخدام خوارزمية ديكسترا. آلة حاسبة مجانية بإدخال بسيط لقائمة الحواف.

آلة حاسبة مصفوفة التجاور — ابنِ مصفوفة رسم بياني عبر الإنترنت

ابنِ واعرض مصفوفة تجاور رسم بياني من إدخال بسيط لقائمة الحواف، مع تسلسل الدرجات. آلة حاسبة مجانية، موزونة أو غير موزونة.

آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت

لوّن رؤوس رسم بياني بحيث لا تشترك عقدتان متصلتان في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.

آلة حاسبة تدفق الشبكة — أقصى تدفق عبر خوارزمية Edmonds-Karp عبر الإنترنت

أوجد أقصى تدفق من مصدر إلى مصرف في رسم بياني موجه ذي سعات باستخدام خوارزمية Edmonds-Karp. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.