מאמר זה מדגים את ההליך ליישום DFS עבור עץ או גרף שסופקו.
כיצד ליישם Depth First Search או DFS עבור גרף ב-Java?
ה-DFS משמש בעיקר לחיפוש גרף על ידי ביקור בכל ענף/קודקוד פעם אחת בדיוק. זה יכול לזהות או לזהות מחזורים בגרף שעוזר במניעת מבוי סתום. זה יכול לשמש כדי לפתור חידות או בעיות מבוך. ניתן ליישם/לנצל את ה-DFS באלגוריתמים של גרפים, סריקת אינטרנט ועיצוב מהדר.
להסבר, בקר בקוד שלהלן של Depth First Search או DFS:
מעמד גרָף {
פְּרָטִי רשימה מקושרת addNode [ ] ;
פְּרָטִי בוליאני חצו [ ] ;
גרָף ( int קודקודים ) {
addNode = חָדָשׁ רשימה מקושרת [ קודקודים ] ;
חצו = חָדָשׁ בוליאני [ קודקודים ] ;
ל ( int אני = 0 ; אני < קודקודים ; אני ++ )
addNode [ אני ] = חָדָשׁ רשימה מקושרת ( ) ;
}
בָּטֵל addEdge ( int src, int הַתחָלָה ) {
addNode [ src ] . לְהוֹסִיף ( הַתחָלָה ) ;
}
תיאור הקוד לעיל:
- ראשית, הכיתה בשם ' גרָף ' נוצר. בתוכו, מכריז ' רשימה מקושרת 'שם' addNode[] ' ומערך סוג בוליאני בשם ' חצו[] '.
- לאחר מכן, העבר את הקודקודים עבור הבנאי של ' גרָף ' מחלקה כפרמטר.
- לאחר מכן, ה' ל לולאה נוצרת כדי לעבור דרך כל צומת של הענף שנבחר.
- בסופו של דבר, סוג הריק ' addEdge() ' משמש להוספת קצוות בין קודקודים. פונקציה זו לוקחת שני פרמטרים: מקור הקודקוד ' src ' וקודקוד היעד ' הַתחָלָה '.
לאחר יצירת הגרף, כעת נוסיף קוד של חיפוש עומק ראשון או DFS עבור הגרף שנוצר לעיל:
בָּטֵל DFS ( int קָדקוֹד ) {
חצו [ קָדקוֹד ] = נָכוֹן ;
מערכת . הַחוּצָה . הדפס ( קָדקוֹד + '' ) ;
איטרטור זֶה = addNode [ קָדקוֹד ] . listIterator ( ) ;
בזמן ( זֶה. hasNext ( ) ) {
int adj = זֶה. הַבָּא ( ) ;
אם ( ! חצו [ adj ] )
DFS ( adj ) ;
}
}
בגוש הקוד שלמעלה:
- קודם ה ' DFS() נוצרת פונקציה שמקבלת ' קָדקוֹד 'כפרמטר. הקודקוד הזה מסומן כביקור.
- לאחר מכן, הדפס את הקודקוד שביקר באמצעות ' out.print() ' שיטה.
- לאחר מכן, צור מופע של ' איטרטור ' החוזר על הקודקודים הסמוכים של הקודקוד הנוכחי.
- אם לא מבקרים את הקודקוד, הוא מעביר את הקודקוד הזה ל' DFS() ' פונקציה.
כעת, הבה ניצור ' רָאשִׁי() ' חלק פונקציה כדי ליצור את הגרף ולאחר מכן להחיל DFS על זה:
פּוּמְבֵּי סטָטִי בָּטֵל רָאשִׁי ( חוּט args [ ] ) {
גרף ק = חָדָשׁ גרָף ( 4 ) ;
ק. addEdge ( 0 , 1 ) ;
ק. addEdge ( 1 , 2 ) ;
ק. addEdge ( 2 , 3 ) ;
ק. addEdge ( 3 , 3 ) ;
מערכת . הַחוּצָה . println ( 'הבא הוא עומק ראשון חציה' ) ;
ק. DFS ( 1 ) ;
}
}
הסבר על הקוד לעיל:
- ראשית, צור אובייקט ' ק ' בשביל ה ' גרָף() ' שיטה.
- לאחר מכן, ה' addEdge() השיטה משמשת להוספת קצוות בין קודקודים מרובים. זה יוצר את המבנה של הגרף שלנו.
- בסופו של דבר, העבר כל ערך קודקוד כארגומנט ל-' שכבר נוצר DFS() ' פונקציה. כדי למצוא את נתיב הקודקוד הזה מהשורש, השתמש באלגוריתם חיפוש עומק ראשון. לדוגמה, ערך של ' 1 ' מועבר ל' DFS() ' פונקציה.
לאחר סיום שלב ההידור:
הפלט מראה שחיפוש העומק הראשון יושם בהצלחה.
סיכום
Depth First Search הוא אלגוריתם חציית גרפים המהווה את הבסיס לאלגוריתמים רבים של גרפים כמו מציאת הנתיב הקצר ביותר, עצים מתפרשים וניתוח קישוריות. הוא מתחיל מצומת השורש ואז נע עמוק ככל האפשר עד לצומת העזיבה או הצומת האחרון של אותו ענף לפני החזרה לאחור. מאמר זה הדגים את ההליך ליישום חיפוש עומק ראשון או DFS עבור גרף ב-Java.