streamalism.org

1. סקירה כללית

במדריך זה, נסתכל על יישום Java של האלגוריתם של Boruvka למציאת עץ מינימום טווח (MST) של גרף משוקלל קצה..

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

2. האלגוריתם של בורובקה

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

2.1. הִיסטוֹרִיָה

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

ז'ורז 'סולין גילה אותו מחדש בשנת 1965 והשתמש בו במחשוב מקביל.

2.2. האלגוריתם

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

בואו נראה זאת בשלבים עם גרף לדוגמא:

• שלב 0: צור גרף
• שלב 1: התחל עם חבורה של עצים לא מחוברים (מספר עצים = מספר קודקודים)
• שלב 2: בעוד שיש עצים לא מחוברים, עבור כל עץ לא מחובר:
  • מצא את קצהו במשקל נמוך יותר
  • הוסף קצה זה כדי לחבר עץ אחר

3. יישום ג'אווה

עכשיו בואו נראה איך נוכל ליישם זאת בג'אווה.

3.1. ה UnionFind מבנה נתונים

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

בואו נגדיר כיתה UnionFind למטרה זו, בשתי שיטות: הִתאַחֲדוּת, ו למצוא:

מעמד ציבורי UnionFind {הורים פרטיים []; דרגות int [] פרטיות; UnionFind ציבורי (int n) {הורים = int int [n]; דרגות = int int [n]; עבור (int i = 0; i <n; i ++) {הורים [i] = i; דרגות [i] = 0; }} מציאת מידע ציבורי (int u) {בזמן (u! = הורים [u]) {u = הורים [u]; } להחזיר אותך; } איחוד חלל ציבורי (int u, int v) {int uParent = find (u); int vParent = מצא (v); אם (uParent == vParent) {return; } אם (מדרג [uParent] מדרג [vParent]) {הורים [vParent] = uPorent; } אחר {הורים [vParent] = הורה; מדורגת [uParent] ++; }}} 

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

לגלות בין אם שני קודקודים u ו v שייכים לאותו עץ, אנו רואים אם מצא (u) מחזיר את אותו הורה כמו מצא (v). ה הִתאַחֲדוּת השיטה משמשת לשילוב עצים. נראה שימוש זה בקרוב.

3.2. הזן גרף מהמשתמש

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

מכיוון שנשתמש ב- JUnit כדי לבדוק את האלגוריתם שלנו, חלק זה נכנס ל- a @לפני שיטה:

@ לפני התקנת הריק הציבורי () {graph = ValueGraphBuilder.undirected (). Build (); graph.putEdgeValue (0, 1, 8); graph.putEdgeValue (0, 2, 5); graph.putEdgeValue (1, 2, 9); graph.putEdgeValue (1, 3, 11); graph.putEdgeValue (2, 3, 15); graph.putEdgeValue (2, 4, 10); graph.putEdgeValue (3, 4, 7); } 

הנה, השתמשנו בזה של גויאבה MutableValueGraph לאחסון הגרף שלנו. ואז השתמשנו ValueGraphBuilder לבנות גרף משוקלל לא מכוון.

השיטה putEdgeValue לוקח שלושה טיעונים, שניים מספר שלםs עבור הקודקודים, והשלישי מספר שלם למשקלו, כמפורט על ידי MutableValueGraphהצהרת סוג כללי.

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

3.3. להפיק עץ מינימלי המשתרע

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

נעשה זאת בשיעור אליו נתקשר BoruvkaMST. ראשית, בואו נכריז על כמה משתנים למשל:

מעמד ציבורי BoruvkaMST {MutableValueGraph static פרטי mst = ValueGraphBuilder.undirected (). build (); פרטי סטטי פרטי int totalWeight; } 

כפי שאנו רואים, אנו משתמשים MutableValueGraph כאן כדי לייצג את ה- MST.

שנית, נגדיר קונסטרוקטור, שבו כל הקסם קורה. נדרש ויכוח אחד - ה גרָף בנינו קודם.

הדבר הראשון שהוא עושה הוא לאתחל א UnionFind מקודקודי גרף הקלט. בתחילה, כל הקודקודים הם הוריהם שלהם, כל אחד בדרגה 0:

BoruvkaMST ציבורי (גרף MutableValueGraph) {int size = graph.nodes (). size (); UnionFind uf = UnionFind חדש (גודל); 

לאחר מכן, ניצור לולאה המגדירה את מספר האיטרציות הנדרש ליצירת ה- MST - לכל היותר לרשום V פעמים או עד שיש לנו קצוות V-1, כאשר V הוא מספר הקודקודים:

עבור (int t = 1; t <size && mst.edges (). size () <size - 1; t = t + t) {EndpointPair [] הקרוב ביותרEdgeArray = EndpointPair חדש [size]; 

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

לאחר מכן נגדיר פנימי ל לולאה כדי לחזור על כל קצוות הגרף כדי לאכלס את שלנו קרוב ביותר Edge Array.

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

עבור (קצה EndpointPair: graph.edges ()) {int u = edge.nodeU (); int v = edge.nodeV (); int uParent = uf.find (u); int vParent = uf.find (v); אם (uParent == vParent) {המשך; } משקל int = graph.edgeValueOrDefault (u, v, 0); אם (הקרוב ביותראדג'אריי [uParent] == ​​null) {הקרוב ביותראדגראיי [uParent] = קצה; } אם (mostEdgeArray [vParent] == ​​null) {הקרוב ביותרEdgeArray [vParent] = edge; } int uParentWeight = graph.edgeValueOrDefault (mostEdgeArray [uParent] .nodeU (), קרוב ביותרEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (mostEdgeArray [vParent] .nodeU (), קרוב ביותרEdgeArray [vParent] .nodeV (), 0); אם (משקל <uParentWeight) {הקרוב ביותרEdgeArray [uParent] = קצה; } אם (משקל <vParentWeight) {הקרוב ביותרEdgeArray [vParent] = קצה; }} 

לאחר מכן נגדיר לולאה פנימית שנייה ליצירת עץ. נוסיף קצוות מהשלב שלעיל לעץ זה מבלי להוסיף את אותו קצה פעמיים. בנוסף, נבצע א הִתאַחֲדוּת על שלנו UnionFind להפיק ולאחסן הורים ודרגות קודקודי העצים שזה עתה נוצרו:

עבור (int i = 0; i <size; i ++) {EdgepointPair edge = הקרוב ביותרEdgeArray [i]; אם (edge! = null) {int u = edge.nodeU (); int v = edge.nodeV (); משקל int = graph.edgeValueOrDefault (u, v, 0); אם (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, weight); משקל כולל + = משקל; uf.union (u, v); }}} 

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

4. בדיקות

לבסוף, בואו נראה JUnit פשוט לאימות היישום שלנו:

@Test public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree () {BoruvkaMST boruvkaMST = BoruvkaMST חדש (גרף); MutableValueGraph mst ​​= boruvkaMST.getMST (); assertEquals (30, boruvkaMST.getTotalWeight ()); assertEquals (4, mst.getEdgeCount ()); } 

כפי שאנו רואים, קיבלנו את MST עם משקל של 30 ו -4 קצוות, זהה לדוגמא הציורית.

5. מסקנה

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

כמו תמיד, קוד המקור זמין ב- GitHub.