האלגוריתם של פריים עם יישום ג'אווה

1. הקדמה

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

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

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

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

הגרף שלעיל הוא גרף משוקלל, לא מכוון, מחובר. הנה MST של גרף זה:

MST של גרף אינו ייחודי. אם לגרף יש יותר מ- MST אחד, אז לכל MST יש אותו משקל קצה כולל.

3. האלגוריתם של פריים

האלגוריתם של Prim לוקח גרף משוקלל, לא מכוון ומחובר כקלט ומחזיר MST של גרף זה כפלט.

זה עובד בצורה חמדנית. בשלב הראשון הוא בוחר קודקוד שרירותי. לְאַחַר מִכֵּן, כל צעד חדש מוסיף את קודקוד העץ הקרוב ביותר שנבנה עד כה עד שלא נותר קודקוד מנותק.

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

בהנחה שהקודקוד השרירותי להפעלת האלגוריתם הוא B, יש לנו שלוש אפשרויות A, C ו- E ללכת. המשקולות המתאימות של הקצוות הן 2, 2 ו- 5, ולכן המינימום הוא 2. במקרה זה, יש לנו שני קצוות במשקל 2, כך שנוכל לבחור באחד מהם (לא משנה איזה). בואו לבחור א ':

כעת יש לנו עץ עם שני קודקודים A ו- B. אנו יכולים לבחור כל אחד מקצוות A או B שעדיין לא הוסיפו המובילים לקודקוד שלא הועבר. אז נוכל לבחור AC, BC או BE.

האלגוריתם של Prim בוחר את המינימום שהוא 2, או BC:

עכשיו יש לנו עץ עם שלושה קודקודים ושלושה קצוות אפשריים להתקדם: CD, CE או BE. AC אינו כלול מכיוון שהוא לא יוסיף קודקוד חדש לעץ. המשקל המינימלי בין שלושת אלה הוא 1.

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

נותר רק קודקוד אחד להצטרף, כך שנוכל לבחור מ- CE ו- BE. המשקל המינימלי שיכול לחבר את העץ שלנו אליו הוא 1, והאלגוריתם של פרים יבחר בו:

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

4. יישום

קודקודים וקצוות יוצרים גרפים, לכן אנו זקוקים למבנה נתונים כדי לאחסן את האלמנטים הללו. בואו ניצור את הכיתה קָצֶה:

מעמד ציבורי Edge {משקל אינטר פרטי; בוליאני פרטי isIncluded = false; }

כל אחד קָצֶה חייב להיות מִשׁקָל מכיוון שהאלגוריתם של פרים עובד על גרפים משוקללים. כלול מראה אם ​​ה קָצֶה קיים בעץ המשתרע המינימלי או לא.

עכשיו, בואו נוסיף את ה- קָדקוֹד מעמד:

וורטקס בכיתה ציבורית {label String private = null; קצוות מפה פרטיים = HashMap חדש (); פרטי בוליאני isVisited = false; }

כל אחד קָדקוֹד יכול להיות אופציונלי תווית. אנו משתמשים ב- קצוות מפה לאחסון חיבורים בין קודקודים. סוף כל סוף, isVisited מראה אם ​​קודקוד ביקר באלגוריתם של פרים עד כה או לא.

בואו ניצור את שלנו מִצטַנֵעַ בכיתה שבה נבצע את ההיגיון:

מחלקה ציבורית ראשונה {גרף רשימה פרטית; }

מספיק רשימה של קודקודים כדי לאחסן את כל הגרף כי בתוך כל אחד מהם קָדקוֹד, יש לנו מַפָּה לזהות את כל הקשרים. בְּתוֹך מִצטַנֵעַ, אנו יוצרים a לָרוּץ() שיטה:

הפעלה בטלנית ציבורית () {if (graph.size ()> 0) {graph.get (0) .setVisited (true); } בעוד (isDisconnected ()) {Edge nextMinimum = Edge חדש (Integer.MAX_VALUE); Vertex nextVertex = graph.get (0); עבור (קודקוד קודקוד: גרף) {אם (קודקוד.isVisited ()) {זוג מועמד = קודקוד.נחץ מינימלי (); אם (candid.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = kandidat.getValue (); nextVertex = candid.getKey (); }}} nextMinimum.setIncluded (true); nextVertex.setVisited (נכון); }}

אנו מתחילים בקביעת האלמנט הראשון של ה- גרף רשימה כמבקר. האלמנט הראשון יכול להיות כל אחד מהקודקודים, בהתאם לסדר שהם הוסיפו לרשימה מלכתחילה. isDisconnected () החזרות נָכוֹן אם יש כאלה קָדקוֹד לא ביקרו עד כה:

פרטי בוליאני isDisconnected () {עבור (קודקוד קודקוד: גרף) {אם (! vertex.isVisited ()) {return true; }} להחזיר שקר; }

אמנם העץ המינימלי המשתרע isDisconnected (), אנו עוקפים את הקודקודים שכבר ביקרנו ונמצא את קָצֶה עם המשקל המינימלי כמועמד ל nextVertex:

צמד ציבורי nextMinimum () {Edge nextMinimum = Edge חדש (Integer.MAX_VALUE); Vertex nextVertex = זה; איטרטור it = edge.entrySet () .iterator (); בעוד (it.hasNext ()) {זוג Map.Entry = it.next (); if (! pair.getKey (). isVisited ()) {if (! pair.getValue (). isIncluded ()) {if (pair.getValue (). getWeight () <nextMinimum.getWeight ()) {nextMinimum = pair .getValue (); nextVertex = pair.getKey (); }}}} להחזיר זוג חדש (nextVertex, nextMinimum); }

אנו מוצאים את המינימום מכולם מוּעֲמָדs בלולאה הראשית ואחסנו אותה nextVertex. ואז, קבענו nextVertex כמבקר. הלולאה נמשכת עד לביקור בכל הקודקודים.

בסופו של דבר, כל אחד קָצֶה עם כלול שווה ל נָכוֹן נוכח.

שים לב שמאז הבא מינימום () זה חוזר בקצוות, מורכבות הזמן של יישום זה היא O (V2). אם נאחסן את הקצוות בתור עדיפות (ממוין לפי משקל) במקום זאת, האלגוריתם יבצע ב O (E יומן V).

5. בדיקות

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

רשימה סטטית ציבורית createGraph () {רשימה גרף = ArrayList חדש (); קודקוד a = קודקוד חדש ("A"); ... ורטקס e = ורטקס חדש ("E"); Edge ab = Edge חדש (2); a.addEdge (b, ab); b.addEdge (a, ab); ... Edge ce = Edge חדש (1); c.addEdge (e, ce); e.addEdge (c, ce); graph.add (א); ... גרף. הוסף (ה); גרף החזרה; }

הקונסטרוקטור של מִצטַנֵעַ הכיתה לוקחת אותה ומאחסנת אותה בתוך הכיתה. נוכל להדפיס את גרף הקלט באמצעות originalGraphToString () שיטה:

Prim prim = Prim חדש (createGraph ()); System.out.println (prim.originalGraphToString ());

הדוגמה שלנו תנפיק:

A --- 2 --- B A --- 3 --- C B --- 5 --- E B --- 2 --- C C --- 1 --- E C --- 1 --- D

כעת, אנו מפעילים את האלגוריתם של פריים ומדפיסים את ה- MST שהתקבל minimumSpanningTreeToString () שיטה:

prim.run (); prim.resetPrintHistory (); System.out.println (prim.minimumSpanningTreeToString ());

לבסוף, אנו מדפיסים את ה- MST שלנו:

A --- 2 --- B B --- 2 --- C C --- 1 --- E C --- 1 --- D

6. מסקנה

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