במאמר זה, נדון באלגוריתם ה-prim. יחד עם האלגוריתם, נראה גם את המורכבות, העבודה, הדוגמה והיישום של האלגוריתם של prim.

לפני שמתחילים את הנושא העיקרי, עלינו לדון במונחים הבסיסיים והחשובים כמו עץ ​​פורש ועץ פורש מינימום.

עץ פורש - עץ פורש הוא תת-גרף של גרף מחובר לא מכוון.

עץ טווח מינימלי - ניתן להגדיר את עץ הפורש המינימלי כעץ הפורש שבו סכום המשקולות של הקצה הוא מינימום. משקל העץ הפורש הוא סכום המשקולות שניתנו לקצוות העץ הפורש.

עכשיו, בואו נתחיל את הנושא המרכזי.

האלגוריתם של פריים הוא אלגוריתם חמדני המשמש למציאת העץ המינימלי המתפרש מגרף. האלגוריתם של Prim מוצא את תת-קבוצת הקצוות הכוללת כל קודקוד של הגרף כך שניתן למזער את סכום המשקולות של הקצוות.

האלגוריתם של Prim מתחיל עם הצומת הבודד וחוקר את כל הצמתים הסמוכים עם כל הקצוות המחברים בכל שלב. נבחרו הקצוות עם המשקלים המינימליים שלא גורמים למחזוריות בגרף.

איך עובד האלגוריתם של הפרים?

האלגוריתם של פרים הוא אלגוריתם חמדני שמתחיל מקודקוד אחד וממשיך להוסיף את הקצוות עם המשקל הקטן ביותר עד להשגת המטרה. השלבים ליישום האלגוריתם של ה-prim ניתנים כדלקמן -

• ראשית, עלינו לאתחל MST עם הקודקוד שנבחר באקראי.
• כעת, עלינו למצוא את כל הקצוות המחברים את העץ בשלב שלמעלה עם הקודקודים החדשים. מהקצוות שנמצאו, בחר את הקצה המינימלי והוסף אותו לעץ.
• חזור על שלב 2 עד שנוצר העץ המינימלי.

היישומים של האלגוריתם של prim הם -

• ניתן להשתמש באלגוריתם של Prim בעיצוב רשת.
• ניתן להשתמש בו כדי ליצור מחזורי רשת.
• זה יכול לשמש גם כדי להניח כבלי חיווט חשמלי.

דוגמה לאלגוריתם של prim

כעת, בואו נראה את פעולת האלגוריתם של prim באמצעות דוגמה. יהיה קל יותר להבין את האלגוריתם של הפרים באמצעות דוגמה.

נניח, גרף משוקלל הוא -

שלב 1 - ראשית, עלינו לבחור קודקוד מהגרף שלמעלה. בוא נבחר ב'.

גודל המסך שלי

שלב 2 - כעת, עלינו לבחור ולהוסיף את הקצה הקצר ביותר מקודקוד B. ישנם שני קצוות מקודקוד B שהם B עד C במשקל 10 וקצה B עד D במשקל 4. בין הקצוות, לקצה BD יש את המשקל המינימלי . אז הוסף אותו ל-MST.

שלב 3 - כעת, שוב, בחר את הקצה עם המשקל המינימלי מבין כל שאר הקצוות. במקרה זה, הקצוות DE ו-CD הם קצוות כאלה. הוסף אותם ל-MST וחקור את הסמוך של C, כלומר, E ו-A. אז, בחר את הקצה DE והוסף אותו ל-MST.

שלב 4 - כעת, בחר את תקליטור הקצה, והוסף אותו ל-MST.

שלב 5 - כעת, בחר את הקצה CA. כאן, איננו יכולים לבחור את הקצה CE מכיוון שהוא יוצר מחזור לגרף. אז, בחר את הקצה CA והוסף אותו ל-MST.

לכן, הגרף שהופק בשלב 5 הוא העץ המינימלי המתפרש בגרף הנתון. עלות ה-MST ניתנת להלן -

עלות MST = 4 + 2 + 1 + 3 = 10 יחידות.

אַלגוֹרִיתְם

 Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT 

מורכבות האלגוריתם של פריים

כעת, בואו נראה את מורכבות הזמן של האלגוריתם של פרים. זמן הריצה של האלגוריתם של ה-prim תלוי בשימוש במבנה הנתונים עבור הגרף ובסדר הקצוות. הטבלה למטה מציגה כמה אפשרויות -

מורכבות זמן

ניתן ליישם את האלגוריתם של Prim בפשטות על ידי שימוש במטריצת הסמיכות או ייצוג גרף רשימת הסמיכות, וכדי להוסיף את הקצה עם המשקל המינימלי יש צורך בחיפוש ליניארי של מערך משקלים. זה דורש O(|V|²) זמן ריצה. ניתן לשפר אותו עוד יותר על ידי שימוש ביישום ערימה כדי למצוא את קצוות המשקל המינימליים בלולאה הפנימית של האלגוריתם.

מורכבות הזמן של האלגוריתם של ה-prim היא O(E logV) או O(V logV), כאשר E הוא המספר. של קצוות, ו-V הוא המס. של קודקודים.

יישום האלגוריתם של Prim

כעת, בואו נראה את היישום של האלגוריתם של prim.

תכנית: כתוב תוכנית ליישום האלגוריתם של prim בשפת C.

 #include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
 	 weight
'); printf(' %d 
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>