גרפים בג'אווה
1. סקירה כללית
במדריך זה, נבין את המושגים הבסיסיים של גרף כמבנה נתונים.
נחקור גם את יישומה ב- Java יחד עם פעולות שונות אפשריות בגרף. נדון גם בספריות Java המציעות יישומי גרף.
2. מבנה נתוני גרף
גרף הוא א מבנה נתונים לאחסון נתונים מחוברים כמו רשת אנשים בפלטפורמת מדיה חברתית.
גרף מורכב מקודקודים וקצוות. קודקוד מייצג את הישות (למשל, אנשים) ו קצה מייצג את היחסים בין ישויות (למשל חברויות של אדם).
בואו נגדיר גרף פשוט כדי להבין זאת טוב יותר:
כאן הגדרנו גרף פשוט עם חמישה קודקודים ושישה קצוות. המעגלים הם קודקודים המייצגים אנשים והקווים המחברים בין שני קודקודים הם קצוות המייצגים חברים בפורטל מקוון.
ישנן מספר וריאציות של גרף פשוט זה בהתאם לתכונות הקצוות. בואו נעבור אותם בקצרה בסעיפים הבאים.
עם זאת, נתמקד רק בגרף הפשוט המוצג כאן עבור דוגמאות Java במדריך זה.
2.1. גרף מכוון
לגרף שהגדרנו עד כה יש קצוות ללא שום כיוון. אם אלו קצוות כוללים כיוון בהם, הגרף המתקבל ידוע כגרף מכוון.
דוגמה לכך יכולה להיות ייצוג מי שולח את בקשת החבר בידידות בפורטל המקוון:
כאן אנו יכולים לראות שלקצוות יש כיוון קבוע. הקצוות יכולים להיות גם דו כיווניים.
2.2. גרף משוקלל
שוב, לגרף הפשוט שלנו יש קצוות שאינם משוחדים או שאינם משוקללים. אם במקום אלה קצוות נושאים משקל יחסי, גרף זה ידוע כגרף משוקלל.
דוגמה ליישום מעשי של זה יכולה להיות ייצוג עד כמה יחסית ידידות בפורטל המקוון היא:
כאן אנו יכולים לראות כי בקצוות יש משקולות המשויכים אליהם. זה מספק משמעות יחסית לקצוות אלה.
3. ייצוגי גרפים
ניתן לייצג גרף בצורות שונות כמו מטריצת סמיכות ורשימת סמיכות. לכל אחד היתרונות והחסרונות שלו במערך אחר.
נציג את ייצוגי הגרפים הללו בסעיף זה.
3.1. מטריקס שכנות
מטריצת סמיכות היא מטריצה מרובעת עם ממדים השווים למספר הקודקודים בגרף.
לאלמנטים של המטריצה בדרך כלל יש ערכים '0' או '1'. ערך של '1' מציין קירבה בין הקודקודים בשורה ובעמודה וערך '0' אחרת.
בואו נראה איך נראית מטריצת הצמידות עבור הגרף הפשוט שלנו מהסעיף הקודם:
ייצוג זה הוא הוגן קל יותר ליישום ויעיל לשאילתה גם כן. עם זאת, זה פחות יעיל ביחס לתפוס מקום.
3.2. רשימת סמיכות
רשימת סמיכות אינה אלא מערך רשימות. גודל המערך שווה למספר הקודקודים בגרף.
הרשימה באינדקס ספציפי של המערך מייצגת את הקודקודים הסמוכים של קודקוד המיוצג על ידי אינדקס מערך זה.
בואו נראה איך נראית רשימת הצמידות עבור הגרף הפשוט שלנו מהסעיף הקודם:
ייצוג זה הוא קשה יחסית ליצור ופחות יעיל לשאילתה. עם זאת, הוא מציע יעילות שטח טובה יותר.
נשתמש ברשימת הצמידות כדי לייצג את הגרף במדריך זה.
4. גרפים בג'אווה
ל- Java אין יישום ברירת מחדל של מבנה נתוני הגרף.
עם זאת, אנו יכולים ליישם את הגרף באמצעות אוספי Java.
נתחיל בהגדרת קודקוד:
ורטקס בכיתה {תווית מחרוזת; קודקוד (תווית מחרוזת) {this.label = label; } // שווה ל- hashCode}ההגדרה של קודקוד לעיל כוללת רק תווית אבל זה יכול לייצג כל ישות אפשרית כמו אדם אוֹ עִיר.
כמו כן, שים לב לכך עלינו לעקוף את שווים() ו hashCode () שיטות כמו אלה נחוצות לעבודה עם אוספי Java.
כפי שדנו קודם, גרף אינו אלא אוסף של קודקודים וקצוות שניתן לייצג כמטריצת סמיכות או כרשימת סמיכות.
בואו נראה כיצד נוכל להגדיר זאת באמצעות רשימת סמיכות כאן:
גרף בכיתה {מפה פרטית adjVertices; // קונסטרוקטור סטנדרטי, גטרים, סטרים} כפי שאנו רואים כאן, הכיתה גרָף משתמש מַפָּה מאוספי Java כדי להגדיר את רשימת הסמיכות.
ישנן מספר פעולות אפשריות במבנה נתוני גרף, כגון יצירה, עדכון או חיפוש דרך הגרף.
נעבור על כמה מהפעולות הנפוצות יותר ונראה כיצד נוכל ליישם אותן בג'אווה.
5. פעולות מוטציה גרפית
ראשית, נגדיר כמה שיטות למוטציה של מבנה נתוני הגרף.
בואו נגדיר שיטות להוסיף ולהסיר קודקודים:
void addVertex (תווית מחרוזת) {adjVertices.putIfAbsent (ורטקס חדש (תווית), ArrayList חדש ()); } בטל removeVertex (תווית מחרוזת) {ורטקס v = ורטקס חדש (תווית); adjVertices.values (). stream (). forEach (e -> e.remove (v)); adjVertices.remove (ורטקס חדש (תווית)); }שיטות אלה פשוט מוסיפות ומסירות אלמנטים מה- קודקודים סט.
עכשיו, בואו נגדיר גם שיטה להוספת קצה:
void addEdge (String label1, String label2) {Vertex v1 = Vertex new (label1); קודקוד v2 = קודקוד חדש (label2); adjVertices.get (v1) .add (v2); adjVertices.get (v2) .add (v1); }שיטה זו יוצרת חדש קָצֶה ומעדכן את הקודקודים הסמוכים מַפָּה.
באופן דומה נגדיר את removeEdge () שיטה:
בטל removeEdge (String label1, String label2) {Vertex v1 = Vertex new (label1); קודקוד v2 = קודקוד חדש (label2); רשימה eV1 = adjVertices.get (v1); רשימה eV2 = adjVertices.get (v2); אם (eV1! = null) eV1.remove (v2); אם (eV2! = null) eV2.remove (v1); }לאחר מכן, בואו נראה כיצד נוכל ליצור את הגרף הפשוט ששרטטנו קודם בשיטות שהגדרנו עד כה:
גרף createGraph () {גרף גרף = גרף חדש (); graph.addVertex ("בוב"); graph.addVertex ("אליס"); graph.addVertex ("מארק"); graph.addVertex ("רוב"); graph.addVertex ("מריה"); graph.addEdge ("בוב", "אליס"); graph.addEdge ("בוב", "רוב"); graph.addEdge ("אליס", "מארק"); graph.addEdge ("רוב", "מארק"); graph.addEdge ("אליס", "מריה"); graph.addEdge ("רוב", "מריה"); גרף החזרה; }נגדיר סוף סוף שיטה לקבלת הקודקודים הסמוכים של קודקוד מסוים:
רשימה getAdjVertices (תווית מחרוזת) {return adjVertices.get (Vertex new (label)); }6. חציית גרף
עכשיו שיש לנו מבנה נתוני גרף ופונקציות ליצור ולעדכן אותו מוגדרים, אנו יכולים להגדיר כמה פונקציות נוספות לחציית הגרף. עלינו לחצות גרף כדי לבצע כל פעולה משמעותית, כמו חיפוש בתוך הגרף.
יש שתי דרכים אפשריות לחצות גרף, חציית עומק ראשונה וחציית רוחב ראשונה.
6.1. מעבר עמוק-ראשון
מעבר עומק ראשון מתחיל בקודקוד השורש שרירותי ו בוחן קודקודים עמוקים ככל האפשר לאורך כל ענף לפני שהוא בוחן קודקודים באותה רמה.
בואו נגדיר שיטה לביצוע המעבר הראשון לעומק:
הגדר עומק FirstFrastTraversal (גרף גרף, שורש מחרוזת) {הגדר ביקר = חדש LinkedHashSet (); מחסנית מחסנית = מחסנית חדשה (); stack.push (שורש); בעוד (! stack.isEmpty ()) {קודקוד מחרוזת = stack.pop (); אם (! ביקר. מכיל (קודקוד)) {ביקר. הוסף (קודקוד); עבור (ורטקס v: graph.getAdjVertices (קודקוד)) {stack.push (v.label); }}} חזרו ביקרו; }פה, אנו משתמשים ב- לַעֲרוֹם לאחסון הקודקודים שצריך לעבור אותם.
בואו נריץ זאת על הגרף שיצרנו בסעיף המשנה הקודם:
assertEquals ("[בוב, רוב, מריה, אליס, מארק]", depthFirstTraversal (גרף, "בוב"). toString ());שים לב שאנחנו משתמשים בקודקוד "בוב" כשורש המעבר שלנו כאן, אך זה יכול להיות כל קודקוד אחר.
6.2. מעבר רוחב ראשון
באופן השוואתי, מעבר רוחב ראשון מתחיל בקודקוד השורש שרירותי ו בוחן את כל הקודקודים הסמוכים באותה רמה לפני שהוא הולך לעומק בגרף.
בואו נגדיר שיטה לביצוע החצייה הראשונה ברוחב:
הגדר breadthFirstTraversal (גרף גרף, שורש מחרוזת) {Set visited = new LinkedHashSet (); תור לתור = LinkedList חדש (); queue.add (שורש); בקרו.וסיף (שורש); בעוד (! queue.isEmpty ()) {קודקוד מחרוזת = queue.poll (); עבור (ורטקס v: graph.getAdjVertices (קודקוד)) {if (! visited.contains (v.label)) {visited.add (v.label); queue.add (v.label); }}} ביקר שוב; }שימו לב כי מעבר רוחב ראשון עושה שימוש ב תוֹר לאחסון הקודקודים שצריך לעבור אותם.
בואו נפעיל שוב את החצייה באותו גרף:
assertEquals ("[בוב, אליס, רוב, מארק, מריה]", breadthFirstTraversal (גרף, "בוב"). toString ());שוב, קודקוד השורש שהוא "בוב" כאן יכול להיות גם כל קודקוד אחר.
7. ספריות Java לגרפים
אין צורך ליישם את הגרף תמיד מאפס ב- Java. ישנן מספר ספריות קוד פתוח ובוגרות המציעות יישומי גרפים.
בכמה סעיפי המשנה הבאים נעבור על כמה מהספריות הללו.
7.1. JGraphT
JGraphT היא אחת הספריות הפופולריות ביותר בג'אווה למבנה נתוני הגרף. זה מאפשר ליצור גרף פשוט, גרף מכוון, גרף משוקלל, בין היתר.
בנוסף, הוא מציע אלגוריתמים אפשריים רבים במבנה נתוני הגרף. אחת ההדרכות הקודמות שלנו מכסה את JGraphT בפירוט רב יותר.
7.2. גויאבה של גוגל
גוגל גויאבה היא קבוצה של ספריות ג'אווה המציעות מגוון פונקציות, כולל מבנה נתוני גרפים ואלגוריתמים שלה.
זה תומך ביצירת פשוט גרָף, ValueGraph, ו רֶשֶׁת. ניתן להגדיר את אלה כ- מִשְׁתַנֶה אוֹ בלתי ניתן לשינוי.
7.3. אפאצ'י קומונס
Apache Commons הוא פרויקט אפאצ'י המציע רכיבי Java לשימוש חוזר. זה כולל Commons Graph המציע ערכת כלים ליצירת וניהול מבנה נתוני גרף. זה מספק גם אלגוריתמים גרפיים נפוצים להפעלת מבנה הנתונים.
7.4. Sourceforge JUNG
Java / Universal Network / Graph (JUNG) היא מסגרת Java המספקת שפה ניתנת להרחבה עבור דוגמנות, ניתוח והדמיה של כל נתונים שניתן לייצג כגרף.
JUNG תומך במספר אלגוריתמים הכוללים רוטינות כמו אשכולות, פירוק ואופטימיזציה.
ספריות אלה מספקות מספר יישומים המבוססים על מבנה נתוני הגרף. יש גם מסגרות חזקות יותר המבוססות על גרפים, כמו Apache Giraph, המשמש כיום בפייסבוק לניתוח הגרף שנוצר על ידי המשתמשים שלהם, ו- Apache TinkerPop, הנפוץ בחלק העליון של מאגרי הגרפים.
8. מסקנה
במאמר זה דנו בגרף כמבנה נתונים יחד עם ייצוגיו. הגדרנו גרף פשוט מאוד בג'אווה באמצעות אוספי ג'אווה וגם הגדרנו מעברים נפוצים עבור הגרף.
שוחחנו בקצרה גם על ספריות שונות הזמינות ב- Java מחוץ לפלטפורמת Java המספקת יישומי גרפים.
כמו תמיד, הקוד לדוגמאות זמין ב- GitHub.
