בודק אם לגרף Java יש מחזור

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

במדריך מהיר זה נלמד כיצד אנו יכולים לזהות מחזור בגרף מכוון נתון.

2. ייצוג גרף

להדרכה זו, נצמד עם ייצוג הגרפים של רשימת הצמידות.

ראשית, נתחיל בהגדרת א קָדקוֹד בג'אווה:

וורטקס בכיתה ציבורית {תווית מחרוזת פרטית; הוויה בוליאנית פרטית; ביקור בוליאני פרטי; סמיכות רשימה רשימה פרטית; ורטקס ציבורי (תווית מחרוזת) {this.label = label; this.adjacencyList = ArrayList חדש (); } ריק ריק addNeighbor (ורטקס סמוך) {this.adjacencyList.add (סמוך); } // גטרים וקובעים}

הנה ה סמוך לרשימה של קודקוד v מחזיקה רשימה של כל הקודקודים הסמוכים ל v. ה הוסף שכן() השיטה מוסיפה קודקוד שכנה לרשימת הצמידות של v.

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

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

אז בואו ונציג במהירות א גרָף בג'אווה:

גרף בכיתה ציבורית {קודקודי רשימה פרטית; גרף ציבורי () {this.vertices = ArrayList חדש (); } בטל פומבי addVertex (קודקוד קודקוד) {this.vertices.add (קודקוד); } addEdge public void (Vertex from, Vertex to) {from.addNeighbor (to); } // ...}

נשתמש ב- addVertex () ו addEdge () שיטות להוסיף קודקודים ושוליים חדשים בגרף שלנו.

3. איתור מחזור

כדי לזהות מחזור בגרף מכוון, נשתמש בווריאציה של DFS חצייה:

  • להרים קודקוד לא נראה v ולסמן את מצבו כ להיות מבקר
  • לכל קודקוד סמוך u שֶׁל v, חשבון:
    • אם u כבר נמצא ב להיות מבקר המדינה, זה אומר בבירור קיים קצה אחורי וכך אותר מחזור
    • אם u עדיין נמצא במצב בלתי מבוקר, נבקר רקורסיבית u בצורה עומק ראשונה
  • עדכן את קודקוד vשל להיות מבקר דגל ל שֶׁקֶר וזה שלה ביקר דגל ל נָכוֹן

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

בואו נסתכל עכשיו על פתרון Java שלנו:

hasCycle בוליאני ציבורי (Source Vertex) {sourceVertex.setBeingVisited (true); עבור (שכנת ורטקס: sourceVertex.getAdjacencyList ()) {if (neighbour.isBeingVisited ()) {// קצה אחורה קיים return true; } אחר אם (! neighbour.isVisited () && hasCycle (שכן)) {return true; }} sourceVertex.setBeingVisited (false); sourceVertex.setVisited (true); להחזיר כוזב; }

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

לגרף מנותק, נצטרך להוסיף שיטת עטיפה נוספת:

hasCycle בוליאני ציבורי () {עבור (קודקוד קודקוד: קודקודים) {אם (! vertex.isVisited () && hasCycle (קודקוד)) {return true; }} להחזיר שקר; }

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

4. בדיקות יישום

בואו ניקח בחשבון את הגרף המכוון למחזור להלן:

אנחנו יכולים לכתוב במהירות JUnit לאימות שלנו hasCycle () שיטה עבור גרף זה:

@ מבט בטל ציבורי givenGraph_whenCycleExists_thenReturnTrue () {קודקוד קודקוד A = קודקוד חדש ("A"); קודקוד קודקוד B = קודקוד חדש ("B"); קודקוד הקודקוד C = קודקוד חדש ("C") קודקוד קודקוד D = קודקוד חדש ("D"); גרף גרף = גרף חדש (); graph.addVertex (קודקוד A); graph.addVertex (קודקוד B); graph.addVertex (קודקוד); graph.addVertex (קודקוד); graph.addEdge (קודקוד A, קודקוד B); graph.addEdge (קודקוד B, קודקוד C); graph.addEdge (קודקוד, קודקוד A); graph.addEdge (קודקוד D, קודקוד C); assertTrue (graph.hasCycle ()); }

הנה, שלנו hasCycle () השיטה הוחזרה נָכוֹן המציין כי הגרף שלנו הוא מחזורי.

5. מסקנה

במדריך זה למדנו כיצד לבדוק אם קיים מחזור בגרף מכוון נתון בג'אווה.

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


$config[zx-auto] not found$config[zx-overlay] not found