Kruskal مقابل Prim
في علوم الكمبيوتر ، تعد خوارزميات Prim’s و Kruskal خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه متصل. الشجرة الممتدة هي رسم بياني فرعي للرسم البياني بحيث ترتبط كل عقدة في الرسم البياني بمسار ، وهو عبارة عن شجرة. كل شجرة ممتدة لها وزن ، والحد الأدنى للأوزان / التكلفة الممكنة لجميع الأشجار الممتدة هو الحد الأدنى للشجرة الممتدة (MST).
المزيد حول خوارزمية Prim’s
تم تطوير الخوارزمية بواسطة عالم الرياضيات التشيكي Vojtěch Jarník في عام 1930 وبعد ذلك بشكل مستقل بواسطة عالم الكمبيوتر Robert C. Prim في عام 1957. أعاد Edsger Dijkstra اكتشافها في عام 1959. يمكن تحديد الخوارزمية في ثلاث خطوات رئيسية ؛
بالنظر إلى الرسم البياني المتصل بالعقد والوزن الخاص بكل حافة ،
1. حدد عقدة عشوائية من الرسم البياني وأضفها إلى الشجرة T (والتي ستكون العقدة الأولى)
2. ضع في اعتبارك أوزان كل حافة متصلة بالعقد الموجودة في الشجرة وحدد الحد الأدنى. أضف الحافة والعقدة في الطرف الآخر من الشجرة T وأزل الحافة من الرسم البياني. (حدد أيًا منها في حالة وجود حد أدنى أو أكثر)
3. كرر الخطوة 2 ، حتى تتم إضافة حواف n-1 إلى الشجرة.
في هذه الطريقة ، تبدأ الشجرة بعقدة تعسفية واحدة وتتوسع من تلك العقدة فصاعدًا مع كل دورة. ومن ثم ، لكي تعمل الخوارزمية بشكل صحيح ، يجب أن يكون الرسم البياني رسمًا بيانيًا متصلًا. يحتوي الشكل الأساسي لخوارزمية Prim على تعقيد زمني لـ O (V2).
المزيد حول خوارزمية Kruskal
ظهرت الخوارزمية التي طورها جوزيف كروسكال في إجراءات الجمعية الرياضية الأمريكية في عام 1956. يمكن أيضًا التعبير عن خوارزمية كروسكال في ثلاث خطوات بسيطة.
بالنظر إلى الرسم البياني الذي يحتوي على عدد n من العقد والوزن الخاص بكل حافة ،
1. حدد القوس الأقل وزنًا للرسم البياني بأكمله وأضفه إلى الشجرة واحذفه من الرسم البياني.
2. من المتبقي حدد الحافة الأقل ترجيحًا ، بطريقة لا تشكل دورة. أضف الحافة إلى الشجرة واحذفها من الرسم البياني. (حدد أيًا منها في حالة وجود حد أدنى أو أكثر)
3. كرر العملية في الخطوة 2.
في هذه الطريقة ، تبدأ الخوارزمية بالحافة الأقل ترجيحًا وتستمر في تحديد كل حافة في كل دورة. لذلك ، في الخوارزمية لا يلزم ربط الرسم البياني. تحتوي خوارزمية Kruskal على تعقيد زمني لـ O (logV)
ما الفرق بين خوارزمية Kruskal و Prim’s Algorithm؟
• يتم تهيئة خوارزمية Prim مع عقدة ، بينما تبدأ خوارزمية Kruskal بحافة.
• تمتد خوارزميات Prim من عقدة إلى أخرى بينما تحدد خوارزمية Kruskal الحواف بطريقة لا يعتمد فيها موضع الحافة على الخطوة الأخيرة.
• في خوارزمية prim ، يجب أن يكون الرسم البياني رسمًا بيانيًا متصلًا بينما يمكن أن يعمل Kruskal على الرسوم البيانية غير المتصلة أيضًا.
• تحتوي خوارزمية Prim على تعقيد زمني لـ O (V2) ، وتعقيد وقت Kruskal هو O (logV).
