الفرق بين كروسكال و بريم: كروسكال فس بريم

< كروسكال فس بريم

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

- <>>>

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

طور الخوارزمية عالم الرياضيات التشيكي فوجتش جارنيك في عام 1930 وبعد ذلك بشكل مستقل من قبل عالم الكمبيوتر روبرت C. بريم في عام 1957. وقد تم اكتشافه من قبل إدسجر ديجكسترا في عام 1959. يمكن ذكر الخوارزمية في ثلاث خطوات رئيسية؛

نظرا للرسم البياني الموصول مع العقد n والوزن الخاص بكل حافة،

1. حدد عقدة عشوائية من الرسم البياني وأضفها إلى شجرة T (التي ستكون العقدة الأولى)

2. النظر في الأوزان من كل حافة متصلة العقد في شجرة وحدد الحد الأدنى. إضافة حافة والعقدة في الطرف الآخر من شجرة T وإزالة الحافة من الرسم البياني. (حدد أي إذا كان هناك حد أدنى أو أكثر من الحد الأدنى)

3. كرر الخطوة 2، حتى تتم إضافة حواف n-1 إلى الشجرة.

في هذه الطريقة، تبدأ الشجرة بعقدة تعسفية واحدة وتتوسع من تلك العقدة فصاعدا مع كل دورة. وبالتالي، لكي تعمل الخوارزمية بشكل صحيح، يجب أن يكون الرسم البياني عبارة عن رسم بياني متصل. الشكل الأساسي للخوارزمية بريم لديه تعقيد الوقت من O (V

2 ^). - 3>>

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

ظهرت الخوارزمية التي وضعها جوزيف كروسكال في أعمال الجمعية الأمريكية الرياضية في عام 1956. ويمكن أيضا التعبير عن خوارزمية كروسكال في ثلاث خطوات بسيطة.

نظرا للرسم البياني مع العقد n ووزن كل حافة،

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

2. من المتبقية تحديد الحافة الأقل المرجحة، بطريقة لا تشكل دورة. إضافة حافة إلى شجرة وحذف من الرسم البياني. (حدد أي إذا كان هناك حد أدنى أو أكثر من الحد الأدنى)

3. كرر العملية في الخطوة 2.

في هذه الطريقة، تبدأ الخوارزمية بحافة أقل مرجحة وتستمر في اختيار كل حافة في كل دورة. لذلك، في خوارزمية الرسم البياني لا يلزم أن تكون متصلا. خوارزمية كروسكال لديها تعقيد الوقت من O (لوغف)

ما هو الفرق بين كروسكال و بريم خوارزمية؟

• خوارزمية بريم تتأهل مع عقدة، في حين خوارزمية كروسكال يبدأ مع حافة.

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

• في خوارزمية بريم، يجب أن يكون الرسم البياني رسما متصلا في حين أن كروسكال يمكن أن تعمل على الرسوم البيانية فصل أيضا.

• خوارزمية بريم لديها تعقيد الوقت من O (V

2 ^{)، و كروسكال تعقيد الوقت هو O (لوغف).}