TechCodeview

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

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

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

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

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

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

כיצד פועל האלגוריתם של קרוסקל?

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

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

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

• ניתן להשתמש באלגוריתם של Kruskal כדי לפרוס חיווט חשמלי בין ערים.
• ניתן להשתמש בו כדי להניח חיבורי LAN.

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

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

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

משקל הקצוות של הגרף לעיל ניתן בטבלה למטה -

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

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

מפת ג'אווה איטרטור

שלב 1 - ראשית, הוסף את הקצה א.ב עם משקל 1 ל-MST.

שלב 2 - הוסף את הקצה שֶׁל עם משקל 2 ל-MST מכיוון שהוא לא יוצר את המחזור.

שלב 3 - הוסף את הקצה לִפנֵי הַסְפִירָה עם משקל 3 ל-MST, מכיוון שהוא לא יוצר שום מחזור או לולאה.

שלב 4 - עכשיו, בחר את הקצה CD עם משקל 4 ל-MST, מכיוון שהוא לא יוצר את המחזור.

שלב 5 - לאחר מכן, בחר את הקצה אבל עם משקל 5. הכללת הקצה הזה תיצור את המחזור, אז זרוק אותו.

שלב 6 - בחר את הקצה AC עם משקל 7. הכללת הקצה הזה תיצור את המחזור, אז זרוק אותו.

שלב 7 - בחר את הקצה מוֹדָעָה עם משקל 10. הכללת הקצה הזה גם תיצור את המחזור, אז זרוק אותו.

אז, העץ המינימלי הסופי המתקבל מהגרף המשוקלל הנתון באמצעות האלגוריתם של Kruskal הוא -

עלות ה-MST היא = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

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

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

 Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END 

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

כעת, בואו נראה את מורכבות הזמן של האלגוריתם של קרוסקל.

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

יישום האלגוריתם של קרוסקל

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

תכנית: כתוב תוכנית ליישום האלגוריתם של kruskal ב-C++.

 #include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>