حواف الشجرة
الطول الكلي
الحواف المفحوصة

  • الحالية
  • في الشجرة
  • ستُغلق دورة

مزيد عن خوارزمية كروسكال

خوارزمية كروسكال

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

كيف يعمل

  1. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة.
  2. اسحب شريط الخطوات للانتقال إلى أي موضع. الحواف التي لم تُجرَّب بعد مدرجة أسفل الرسم البياني، الأقصر أولًا.
  3. انتبه إلى الحواف المرسومة بخط أحمر متقطع: إنها ستُغلق دورة. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.

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

رتّب كل الحواف من الأقصر إلى الأطول. ابدأ وكل عقدة جزء قائم بذاته. جرّب الحواف بالترتيب: إذا ربطت حافة جزأين مختلفين، تدخل الشجرة ويصبح الجزآن جزءًا واحدًا؛ وإذا كان طرفاها في الجزء نفسه بالفعل، فستُغلق دورة، فتخطَّها. توقف عندما يصبح كل شيء جزءًا واحدًا، وهذا يحدث بعد حواف عددها أقل من عدد العقد بواحدة، وكثيرًا قبل تجربة آخر حافة بوقت طويل.

اتحاد-بحث

لكل حافة، على خوارزمية كروسكال أن تسأل: هل طرفاها متصلان بالفعل؟ وتجيب بنية اتحاد-بحث عن ذلك بسرعة: لكل جزء عقدة ممثِّلة واحدة، وتتبع find الروابط حتى تصل إليها، وتربط union ممثِّلًا بالآخر. وبحيلتين بسيطتين، ضغط المسار والدمج حسب الحجم، يستغرق كل سؤال وقتًا ثابتًا تقريبًا، فيكون ترتيب الحواف أبطأ جزء، ويزداد عمله بنسبة E log E.

الأسئلة المتداولة

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

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

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

تُغلق الحافة دورة تمامًا عندما يكون طرفاها متصلين بالفعل عبر حواف مختارة. وتتتبع بنية اتحاد-بحث أي العقد متصلة، وتجيب عن هذا السؤال في لحظة تقريبًا.

لماذا تنجح خوارزمية كروسكال؟

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

متى أستخدم كروسكال بدلًا من بريم؟

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

هل يُرسل الرسم البياني إلى أي مكان؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر