Kruskal נגד Prim
במדעי המחשב, האלגוריתמים של Prim ושל Kruskal הם אלגוריתם חמדני שמוצא עץ פורש מינימלי עבור גרף לא מכוון מחובר. עץ פורש הוא תת-גרף של גרף כך שכל צומת בגרף מחובר בנתיב, שהוא עץ. לכל עץ פורש יש משקל, והעלות המינימלית האפשרית של כל העצים הפורשים היא עץ הפורש המינימלי (MST).
עוד על האלגוריתם של Prim
האלגוריתם פותח על ידי המתמטיקאי הצ'כי Vojtěch Jarník בשנת 1930 ומאוחר יותר באופן עצמאי על ידי מדען המחשב רוברט C. Prim בשנת 1957. הוא התגלה מחדש על ידי Edsger Dijkstra בשנת 1959. ניתן לקבוע את האלגוריתם בשלושה שלבים מרכזיים;
בהינתן הגרף המחובר עם n צמתים ומשקל בהתאמה של כל קצה, 1. בחר צומת שרירותי מהגרף והוסף אותו לעץ T (שיהיה הצומת הראשון)
2. שקול את המשקולות של כל קצה המחובר לצמתים בעץ ובחר את המינימום. הוסף את הקצה והצומת בקצה השני של העץ T והסר את הקצה מהגרף. (בחר אחד אם קיימים שניים או יותר מינימום)
3. חזור על שלב 2, עד שיתווספו n-1 קצוות לעץ.
בשיטה זו, העץ מתחיל עם צומת שרירותי יחיד ומתרחב מאותו צומת ואילך עם כל מחזור. מכאן שכדי שהאלגוריתם יעבוד כמו שצריך, הגרף צריך להיות גרף מחובר. לצורה הבסיסית של האלגוריתם של Prim יש מורכבות זמן של O(V2).
עוד על האלגוריתם של Kruskal
האלגוריתם שפיתח ג'וזף קרוסקל הופיע בהליכים של האגודה האמריקנית למתמטיקה בשנת 1956. ניתן לבטא את האלגוריתם של קרוסקל גם בשלושה שלבים פשוטים.
בהינתן הגרף עם n צמתים ומשקל בהתאמה של כל קצה, 1. בחר את הקשת עם המשקל הנמוך ביותר של כל הגרף והוסף לעץ ומחק מהגרף.
2. מהנותרים בחר את הקצה הכי פחות משוקלל, באופן שלא יוצר מחזור. הוסף את הקצה לעץ ומחק מהגרף. (בחר אחד אם קיימים שניים או יותר מינימום)
3. חזור על התהליך בשלב 2.
בשיטה זו, האלגוריתם מתחיל עם הקצה המשוקלל הנמוך ביותר וממשיך לבחור כל קצה בכל מחזור. לכן, באלגוריתם הגרף לא צריך להיות מחובר. לאלגוריתם של Kruskal יש מורכבות זמן של O(logV)
מה ההבדל בין האלגוריתם של Kruskal ו-Prim?
• האלגוריתם של Prim מאתחל עם צומת, בעוד שהאלגוריתם של Kruskal מתחיל עם Edge.
• האלגוריתמים של Prim משתרעים בין צומת אחד למשנהו בעוד שהאלגוריתם של Kruskal בוחר את הקצוות באופן שמיקום הקצה אינו מבוסס על הצעד האחרון.
• באלגוריתם של prim, הגרף חייב להיות גרף מחובר בעוד שה-Krusskal's יכול לתפקד גם על גרפים מנותקים.
• לאלגוריתם של Prim יש מורכבות זמן של O(V2), ומורכבות הזמן של Kruskal היא O(logV).
