ما هي خوارزمية Prims المستخدمة؟

2024 مؤلف: Lynn Donovan | [email protected]. آخر تعديل: 2023-12-15 23:43

في علوم الكمبيوتر ، بريم (المعروف أيضًا باسم Jarník's) الخوارزمية جشع الخوارزمية هذا يعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه. هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس ، حيث يتم تقليل الوزن الإجمالي لجميع الحواف في الشجرة.

إلى جانب ذلك ، ما هي خوارزمية Kruskal المستخدمة؟

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

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

ثانيًا ، ما هو أفضل خوارزمية Prims و Kruskal؟

خوارزمية Kruskal : ينفذ أفضل المواقف غير النمطية (الرسوم البيانية المتفرقة) لأنها تستخدم هياكل بيانات أبسط. خوارزمية بريم : يكون أسرع بشكل ملحوظ في الحد عندما يكون لديك رسم بياني كثيف مع عدد أكبر من الرؤوس.

ما هو الوقت المعقد لخوارزمية بريمس؟

وبالتالي فإنه يستخدم مصفوفة واحدة من الأعداد الصحيحة لتعريف الرسم البياني الفرعي للرسم البياني. ال تعقيد الوقت هي O (VlogV + ElogV) = O (ElogV) ، مما يجعلها مماثلة لـ خوارزمية كروسكال . لكن، خوارزمية بريم يمكن تحسينها باستخدام Fibonacci Heaps (cf Cormen) إلى O (E + logV).