עץ פורש מינימלי

יום שלישי, מאי 25, 2010

בעיית העץ הפורש המינימלי היא בעייה קלאסית בתחום תורת הגראפים. לא כולם אוהבים או מתמצאים במתימטיקה, אלא שדווקא תורת הגראפים היא תחום קל להבנה אינטואיטיבית – ללא נוסחאות, ואפשר בקלות להבין מה הבעייה ואפילו כיצד לפתור אותה- מכיוון שהבעיות ויזואליות; בעיקר בבעייה זו. אשתמש באלגוריתם של Prim אותו אממש בעזרת CTE רקורסיבי: 1. נמספר את הקשתות בסדר עולה לפי האורך, ונתחיל עם הקטנה ביותר. 2. "נצבור" בעמודה S_in את הקשתות הכלולות בעץ הפורש המינימלי (כלומר- שני הקודקודים של כל קשת). 3. כל...