TechCodeview

לפני שנסתכל על ההבדלים בין BFS ל- DFS, עלינו לדעת תחילה על BFS ו- DFS בנפרד.

מה זה BFS?

BFS מייצג חיפוש רוחב ראשון . זה ידוע גם בשם חציית סדר ברמה . מבנה נתוני התור משמש למעבר ב-Badth First Search. כאשר אנו משתמשים באלגוריתם BFS עבור המעבר בגרף, אנו יכולים להתייחס לכל צומת כצומת שורש.

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

מחרוזת ב-char java

נניח שאנו רואים את צומת 0 כצומת שורש. לכן, המעבר יתחיל מצומת 0.

ברגע שצומת 0 מוסר מהתור, הוא מודפס ומסומן כ-a צומת ביקר.

ברגע שצומת 0 יוסר מהתור, הצמתים הסמוכים של צומת 0 יוכנסו לתור כמוצג להלן:

כעת הצומת 1 יוסר מהתור; הוא מודפס ומסומן כצומת ביקר

ברגע שצומת 1 יוסר מהתור, כל הצמתים הסמוכים של צומת 1 יתווספו לתור. הצמתים הסמוכים של צומת 1 הם 0, 3, 2, 6 ו-5. אבל עלינו להכניס רק צמתים שלא ביקרו בתור. מכיוון שהצמתים 3, 2, 6 ו-5 אינם ביקרו; לכן, צמתים אלה יתווספו בתור כפי שמוצג להלן:

הצומת הבא הוא 3 בתור. אז, צומת 3 יוסר מהתור, הוא מודפס ומסומן כביקור כפי שמוצג להלן:

ברגע שצומת 3 יוסר מהתור, כל הצמתים הסמוכים של צומת 3 מלבד הצמתים שבהם ביקרו יתווספו לתור. הצמתים הסמוכים של צומת 3 הם 0, 1, 2 ו-4. מכיוון שצמתים 0, 1 כבר ביקרו, והצומת 2 קיים בתור; לכן, עלינו להוסיף רק צומת 4 בתור.

השחקנית סאי פאלאווי

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

ברגע שצומת 2 יוסר מהתור, כל הצמתים הסמוכים של צומת 2 מלבד הצמתים שבהם ביקרו יתווספו לתור. הצמתים הסמוכים של צומת 2 הם 1, 3, 5, 6 ו-4. מכיוון שהצמתים 1 ו-3 כבר ביקרו, וכבר נוספו 4, 5, 6 בתור; לכן, אנחנו לא צריכים להוסיף שום צומת בתור.

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

ברגע שצומת 5 יוסר מהתור, כל הצמתים הסמוכים של צומת 5 מלבד הצמתים שבהם ביקרו יתווספו לתור. הצמתים הסמוכים של צומת 5 הם 1 ו-2. מכיוון ששני הצמתים כבר ביקרו; לכן, אין קודקוד להוספת תור.

הצומת הבא הוא 6. אז, 6 יימחק מהתור. זה מודפס ומסומן כמו ביקר כפי שמוצג להלן:

java mvc

ברגע שהצומת 6 יוסר מהתור, כל הצמתים הסמוכים של צומת 6 מלבד הצמתים שבהם ביקרו יתווספו לתור. הצמתים הסמוכים של צומת 6 הם 1 ו-4. מכיוון שצומת 1 כבר ביקר וצומת 4 כבר מתווסף בתור; לכן, אין קודקוד להוספת התור.

הרכיב הבא בתור הוא 4. לכן, 4 יימחק מהתור. זה מודפס ומסומן כביקור.

ברגע שהצומת 4 יוסר מהתור, כל הצמתים הסמוכים של צומת 4 מלבד הצמתים שבהם ביקר יתווספו לתור. הצמתים הסמוכים של צומת 4 הם 3, 2 ו-6. מכיוון שכל הצמתים הסמוכים כבר ביקרו; לכן, אין קודקוד להוספת בתור.

מה זה DFS?

DFS ראשי תיבות של Depth First Search. במעבר DFS, נעשה שימוש במבנה הנתונים מחסנית, שפועל על עיקרון LIFO (Last In First Out). ב-DFS, ניתן להתחיל את המעבר מכל צומת, או שאנו יכולים לומר שכל צומת יכול להיחשב כצומת שורש עד שצומת השורש לא מוזכר בבעיה.

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

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

שקול את צומת 0 כצומת שורש.

ראשית, נכניס את האלמנט 0 לערימה כפי שמוצג להלן:

לצומת 0 יש שני צמתים סמוכים, כלומר, 1 ו-3. כעת נוכל לקחת רק צומת סמוך אחד, או 1 או 3, למעבר. נניח שאנו רואים את צומת 1; לכן, 1 מוכנס לערימה ומודפס כמוצג להלן:

להגדיר מחשב

כעת נסתכל על הקודקודים הסמוכים של צומת 1. הקודקודים הסמוכים שלא ביקרו של צומת 1 הם 3, 2, 5 ו-6. אנו יכולים לשקול כל אחד מארבעת הקודקודים הללו. נניח שניקח את צומת 3 ונכניס אותו לערימה כפי שמוצג להלן:

קחו בחשבון את הקודקודים הסמוכים שלא ביקרו של צומת 3. הקודקודים הסמוכים שלא ביקרו של צומת 3 הם 2 ו-4. אנחנו יכולים לקחת כל אחד מהקודקודים, כלומר 2 או 4. נניח שניקח את קודקוד 2 ונכניס אותו לערימה כפי שמוצג להלן:

הקודקודים הסמוכים שלא ביקרו של צומת 2 הם 5 ו-4. אנחנו יכולים לבחור אחד מהקודקודים, כלומר 5 או 4. נניח שניקח את קודקוד 4 ונכניס לערימה כמוצג להלן:

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

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

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

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

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

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

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

מודגש ב-CSS

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

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

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

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

הבדלים בין BFS ל- DFS

להלן ההבדלים בין BFS ל- DFS: