streamalism.org

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

במדריך זה נחקור את החיפוש 'עומק ראשון' בג'אווה.

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

בסעיפים הבאים נבחן תחילה את היישום של עץ ואז גרף.

כדי לראות כיצד ליישם מבנים אלה ב- Java, עיין בהדרכות הקודמות שלנו בנושא Binary Tree and Graph.

2. חיפוש בעומק העץ הראשון

ישנם שלושה פקודות שונות לחציית עץ באמצעות DFS:

1. הזמנה מוקדמת
2. מעבר לפי הזמנה
3. מעבר לאחר הזמנה

2.1. הזמנה מוקדמת

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

אנחנו יכולים פשוט ליישם חציית הזמנה מראש באמצעות רקורסיה:

• לְבַקֵר נוֹכְחִי צוֹמֶת
• לַחֲצוֹת שמאלה עץ משנה
• לַחֲצוֹת ימין עץ משנה

חלל ציבורי traversePreOrder (צומת צומת) {if (node! = null) {visit (node.value); traversePreOrder (node.left); traversePreOrder (node.right); }}

אנחנו יכולים גם ליישם מעבר הזמנה מראש ללא רקורסיה.

כדי ליישם מעבר מקדים איטרטיבי, נצטרך לַעֲרוֹם, ואנחנו נעבור את השלבים הבאים:

• לִדחוֹף שורש ב- s שלנונַעַץ
• בזמן לַעֲרוֹם זה לא ריק
  • פּוֹפּ נוֹכְחִי צוֹמֶת
  • לְבַקֵר נוֹכְחִי צוֹמֶת
  • לִדחוֹף ימין ילד, אם כן שמאלה ילד ל לַעֲרוֹם

חלל ציבורי traversePreOrderWithoutRecursion () {מחסנית מחסנית = מחסנית חדשה (); צומת הנוכחי = שורש; stack.push (שורש); בעוד (! stack.isEmpty ()) {current = stack.pop (); ביקור (current.value); אם (current.right! = null) {stack.push (current.right); } אם (current.left! = null) {stack.push (current.left); }}}

2.2. מעבר לפי הזמנה

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

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

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

חלל ציבורי traverseInOrder (צומת צומת) {if (node! = null) {traverseInOrder (node.left); בקר (node.value); traverseInOrder (node.right); }}

אנחנו יכולים גם ליישם מעבר דרכים ללא רקורסיהגם:

• לִדחוֹף שורש צומת אל סנַעַץ
• בעוד שנַעַץ זה לא ריק
  • תמשיך לדחוף שמאלה ילד אל לַעֲרוֹם, עד שנגיע נוֹכְחִי הילד השמאלי ביותר של הצומת
  • לְבַקֵר נוֹכְחִי צוֹמֶת
  • לִדחוֹף ימין ילד אל לַעֲרוֹם

חלל ריק traverseInOrderWithoutRecursion () {מחסנית מחסנית = מחסנית חדשה (); צומת הנוכחי = שורש; stack.push (שורש); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (הנוכחי); } הנוכחי = stack.pop (); ביקור (current.value); אם (current.right! = null) {current = current.right; stack.push (הנוכחי); }}}

2.3. מעבר לאחר הזמנה

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

אנחנו יכולים לעקוב אחר הקודם שלנו פתרון רקורסיבי:

חלל ציבורי traversePostOrder (צומת צומת) {if (node! = null) {traversePostOrder (node.left); traversePostOrder (node.right); בקר (node.value); }}

או, אנחנו יכולים גם ליישם מעבר לאחר ההזמנה ללא רקורסיה:

• לִדחוֹף שורש צומת ב סנַעַץ
• בעוד שנַעַץ זה לא ריק
  • בדוק אם כבר חצינו את עץ העץ השמאלי והימני
  • אם לא אז דחפו ימין ילד ו שמאלה ילד אל לַעֲרוֹם

חלל ציבורי traversePostOrderWithoutRecursion () {מחסנית מחסנית = מחסנית חדשה (); צומת prev = שורש; צומת הנוכחי = שורש; stack.push (שורש); בעוד (! stack.isEmpty ()) {current = stack.peek (); hasChild בוליאני = (current.left! = null || current.right! = null); בוליאני isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); אם (! hasChild || isPrevLastChild) {current = stack.pop (); ביקור (current.value); prev = הנוכחי; } אחר {if (current.right! = null) {stack.push (current.right); } אם (current.left! = null) {stack.push (current.left); }}}}

3. גרף חיפוש עומק ראשון

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

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

נראה שתי יישומים עבור גרף DFS, עם רקורסיה וללא רקורסיה.

3.1. גרף DFS עם רקורסיה

ראשית, נתחיל בפשטות עם רקורסיה:

• נתחיל מצומת נתון
• סימן נוֹכְחִי הצומת כפי שביקר
• לְבַקֵר נוֹכְחִי צוֹמֶת
• חצו את הקודקודים הסמוכים

חלל ציבורי dfs (התחלה int) {בוליאני [] isVisited = בוליאני חדש [adjVertices.size ()]; dfsRecursive (התחל, isVisited); } ריק ריק dfsRecursive (int הנוכחי, בוליאני [] isVisited) {isVisited [הנוכחי] = נכון; ביקור (הנוכחי); עבור (int dest: adjVertices.get (current)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. גרף DFS ללא רקורסיה

אנו יכולים גם ליישם DFS גרף ללא רקורסיה. פשוט נשתמש ב- לַעֲרוֹם:

• נתחיל מצומת נתון
• לִדחוֹף הַתחָלָה צומת לתוך לַעֲרוֹם
• בזמן לַעֲרוֹם לא ריק
  • סימן נוֹכְחִי צומת כפי שביקר
  • לְבַקֵר נוֹכְחִי צוֹמֶת
  • דחף קודקודים סמוכים שלא נראים

חלל ציבורי dfsWithoutRecursion (int התחלה) {Stack stack = stack חדש (); בוליאני [] isVisited = בוליאני חדש [adjVertices.size ()]; stack.push (התחל); בעוד (! stack.isEmpty ()) {int הנוכחי = stack.pop (); isVisited [הנוכחי] = נכון; ביקור (הנוכחי); עבור (int dest: adjVertices.get (current)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. מיון טופולוגי

יש הרבה יישומים לחיפוש עומק גרפי-ראשון. אחד היישומים המפורסמים עבור DFS הוא מיון טופולוגי.

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

כדי למיין טופולוגית, נצטרך תוספת פשוטה ל- DFS שהטמענו זה עתה:

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

ציבורי רשימה topologicalSort (int התחל) {LinkedList תוצאה = חדש LinkedList (); בוליאני [] isVisited = בוליאני חדש [adjVertices.size ()]; topologicalSortRecursive (התחל, isVisited, תוצאה); תוצאת החזרה; } חלל פרטי topologicalSortRecursive (int current, boolean [] isVisited, LinkedList result) {isVisited [current] = true; עבור (int dest: adjVertices.get (current)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } result.addFirst (הנוכחי); }

4. מסקנה

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

קוד המקור המלא זמין ב- GitHub.