streamalism.org

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

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

2. עץ פורש

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

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

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

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

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

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

בואו להפעיל את האלגוריתם של קרוסקאל עבור עץ מינימלי המשתרע על הגרף לדוגמה שלנו שלב אחר שלב:

ראשית, אנו בוחרים את הקצה (0, 2) מכיוון שיש לו את המשקל הקטן ביותר. לאחר מכן, אנו יכולים להוסיף קצוות (3, 4) ו- (0, 1) מכיוון שהם אינם יוצרים מחזורים כלשהם. כעת המועמד הבא הוא קצה (1, 2) עם משקל 9. עם זאת, אם נכלול קצה זה, נפיק מחזור (0, 1, 2). לכן, אנו משליכים את הקצה הזה וממשיכים לבחור את הקטן ביותר הבא. לבסוף, האלגוריתם מסתיים על ידי הוספת הקצה (2, 4) של משקל 10.

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

4. זיהוי מחזור עם סט מפוצל

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

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

4.1. סט מבודד ובניית עצים משתרעת

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

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

לדוגמא, במינימום העיצוב המינימלי הנ"ל, ראשית יש לנו 5 קבוצות צומת: {0}, {1}, {2}, {3}, {4}. כאשר אנו בודקים את הקצה הראשון (0, 2), שני הצמתים שלו נמצאים בקבוצות צומת שונות. לכן, אנו יכולים לכלול קצה זה ולמזג את {0} ואת {2} לקבוצה אחת {0, 2}.

אנו יכולים לבצע פעולות דומות בקצוות (3, 4) ו- (0, 1). מערכי הצומת הופכים ל {0, 1, 2} ו- {3, 4}. כאשר אנו בודקים את הקצה הבא (1, 2), אנו יכולים לראות ששני הצמתים של קצה זה נמצאים באותה קבוצה. לכן, אנו משליכים את הקצה הזה וממשיכים לבדוק את הבא. לבסוף, הקצה (2, 4) מספק את מצבנו, ואנחנו יכולים לכלול אותו בעץ המינימלי המשתרע.

4.2. יישום קבוצה לא נפרדת

אנו יכולים להשתמש במבנה עץ כדי לייצג קבוצה לא צמודה. לכל צומת יש הוֹרֶה מצביע להפניה לצומת האב שלו. בכל קבוצה, יש צומת שורש ייחודי המייצג קבוצה זו. לצומת השורש יש הפניה עצמית הוֹרֶה מַצבִּיעַ.

בואו נשתמש במחלקה של Java כדי להגדיר את המידע על סט המפרק:

מחלקה ציבורית DisjointSetInfo {privateNteger parentNode; DisjointSetInfo (הורה שלם) {setParentNode (הורה); } // קובעי סטנדרטים וגטרים}

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

בטל initDisjointSets (int totalNodes) {nodes = ArrayList חדש (totalNodes); עבור (int i = 0; i <totalNodes; i ++) {nodes.add (DisjointSetInfo (i) חדש); }} 

4.3. מצא מבצע

כדי למצוא את הסט שאליו שייך צומת, נוכל לעקוב אחר שרשרת האב של הצומת כלפי מעלה עד שנגיע לצומת הבסיס:

איתור שלם (צומת שלם) {אב שלם = nodes.get (צומת) .getParentNode (); אם (parent.equals (node)) {node return; } אחר {החזר למצוא (הורה); }}

אפשר לקבל מבנה עצים מאוד לא מאוזן לסט לא נפרד. אנחנו יכולים לשפר את למצוא פעולה באמצעות עמ 'דחיסה טֶכנִיקָה.

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

נתיב שלםCompressionFind (צומת שלם) {DisjointSetInfo setInfo = nodes.get (node); הורה שלם = setInfo.getParentNode (); אם (parent.equals (node)) {node return; } אחר {parenterode שלם = מצא (הורה); setInfo.setParentNode (parentNode); להחזיר parentNode; }}

4.4. מבצע האיחוד

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

איחוד חלל (Integer rootU, Integer rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); setInfoU.setParentNode (rootV); }

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

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

כדי להשיג זאת, ראשית נוסיף א דַרגָה רכוש ל DisjointSetInfo מעמד:

מחלקה ציבורית DisjointSetInfo {parentNode פרטי שלם שלם; דירוג אינטי פרטי; DisjointSetInfo (הורה שלם) {setParentNode (הורה); setRank (0); } // קובעי סטנדרטים וגטרים}

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

void unionByRank (int rootU, int rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); DisjointSetInfo setInfoV = nodes.get (rootV); int rankU = setInfoU.getRank (); int rankV = setInfoV.getRank (); אם (rankU <rankV) {setInfoU.setParentNode (rootV); } אחר {setInfoV.setParentNode (rootU); אם (rankU == rankV) {setInfoU.setRank (rankU + 1); }}}

4.5. זיהוי מחזור

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

גילוי מחזור בוליאני (שלם u, שלם v) {rootU שלם שלם = pathCompressionFind (u); מספר שלם rootV = pathCompressionFind (v); אם (rootU.equals (rootV)) {return true; } unionByRank (rootU, rootV); להחזיר כוזב; } 

איתור המחזור, עם איחוד לפי דרגה טכניקה בלבד, יש זמן ריצה של O (logV). אנו יכולים להשיג ביצועים טובים יותר עם שניהם דחיסת נתיב ו איחוד לפי דרגה טכניקות. זמן הריצה הוא O (α (V)), איפה α (V) הוא פונקציית Ackermann ההפוכה של המספר הכולל של הצמתים. זהו קבוע קטן הנמצא פחות מ -5 בחישובים שלנו בעולם האמיתי.

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

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

להשתמש ValueGraphראשית עלינו להוסיף את התלות בגויאבה לפרויקטים שלנו pom.xml קוֹבֶץ:

     com.google.guava גויאבה 28.1-jre 

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

ValueGraph spanningTree (גרף ValueGraph, minSpanningTree בוליאני) {Set edge = graph.edges (); רשימת edgeList = ArrayList חדש (קצוות); אם (minSpanningTree) {edgeList.sort (Comparator.comparing (e -> graph.edgeValue (e) .get ())); } אחר {edgeList.sort (Collections.reverseOrder (Comparator.comparing (e -> graph.edgeValue (e) .get ()))); } int totalNodes = graph.nodes (). size (); CycleDetector cycleDetector = CycleDetector חדש (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); עבור (EndpointPair edge: edgeList) {if (cycleDetector.detectCycle (edge.nodeU (), edge.nodeV ())) {המשך; } spanningTree.putEdgeValue (edge.nodeU (), edge.nodeV (), graph.edgeValue (edge) .get ()); edgeCount ++; אם (edgeCount == totalNodes - 1) {break; }} להחזיר spanningTree; }

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

ואז אנו משתמשים בלולאה כדי לעבור על רשימת הקצוות הממוינת. בכל איטרציה, אנו בודקים אם ייווצר מחזור על ידי הוספת הקצה לסט הקצוות הנוכחי של העץ. לולאה זו עם זיהוי המחזור אורכת לכל היותר O (ElogV) זְמַן.

לכן, זמן הריצה הכללי הוא O (ELogE + ELogV). מאז הערך של ה נמצא בסולם של O (V2), מורכבות הזמן של האלגוריתם של קרוסקאל היא O (ElogE) אוֹ O (ElogV).

6. מסקנה

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