במאמר זה, נדון באלגוריתם BFS במבנה הנתונים. חיפוש רוחב ראשון הוא אלגוריתם חציית גרפים שמתחיל לעבור את הגרף מצומת השורש וחוקר את כל הצמתים הסמוכים. לאחר מכן, הוא בוחר את הצומת הקרוב ביותר וחוקר את כל הצמתים שלא נחקרו. בזמן שימוש ב-BFS למעבר, כל צומת בגרף יכול להיחשב כצומת השורש.
ישנן דרכים רבות לחצות את הגרף, אך ביניהן, BFS היא הגישה הנפוצה ביותר. זהו אלגוריתם רקורסיבי לחיפוש בכל הקודקודים של מבנה נתונים של עץ או גרף. BFS מכניס כל קודקוד של הגרף לשתי קטגוריות - ביקר ולא ביקר. הוא בוחר צומת בודד בגרף ולאחר מכן מבקר בכל הצמתים הסמוכים לצומת שנבחר.
יישומים של אלגוריתם BFS
היישומים של אלגוריתם רוחב-ראשון ניתנים כדלקמן -
- ניתן להשתמש ב-BFS כדי למצוא את המיקומים הסמוכים ממיקום מקור נתון.
- ברשת עמית לעמית, אלגוריתם BFS יכול לשמש כשיטת מעבר למציאת כל הצמתים הסמוכים. רוב לקוחות הטורנט, כגון BitTorrent, uTorrent וכו' משתמשים בתהליך זה כדי למצוא 'זרעים' ו'עמיתים' ברשת.
- ניתן להשתמש ב-BFS בסורקי אינטרנט ליצירת אינדקסים של דפי אינטרנט. זהו אחד האלגוריתמים העיקריים שניתן להשתמש בהם לאינדקס דפי אינטרנט. הוא מתחיל לעבור מדף המקור ועוקב אחר הקישורים המשויכים לדף. כאן, כל דף אינטרנט נחשב כצומת בגרף.
- BFS משמש כדי לקבוע את הנתיב הקצר ביותר ואת העץ המינימלי.
- BFS משמש גם בטכניקה של צ'ייני כדי לשכפל את אוסף האשפה.
- ניתן להשתמש בו בשיטת ford-Fulkerson כדי לחשב את הזרימה המקסימלית ברשת זרימה.
אַלגוֹרִיתְם
השלבים המעורבים באלגוריתם BFS לחקור גרף ניתנים כדלקמן -
שלב 1: SET STATUS = 1 (מצב מוכן) עבור כל צומת ב-G
שלב 2: הציבו את צומת ההתחלה A והגדרו את הסטטוס שלו = 2 (מצב המתנה)
מערך מחרוזות
שלב 3: חזור על שלבים 4 ו-5 עד שהתור ריק
שלב 4: תורידו צומת N. עבדו אותו והגדרו את STATUS שלו = 3 (מצב מעובד).
שלב 5: הציבו את כל השכנים של N שנמצאים במצב מוכן (שהסטטוס שלהם = 1) והגדר
הסטטוס שלהם = 2
(מצב המתנה)
[סוף לולאה]
שלב 6: יְצִיאָה
דוגמה לאלגוריתם BFS
כעת, בואו נבין את פעולתו של אלגוריתם BFS באמצעות דוגמה. בדוגמה המובאת להלן, יש גרף מכוון בעל 7 קודקודים.
בגרף שלמעלה, ניתן למצוא את הנתיב המינימלי 'P' באמצעות ה-BFS שיתחיל מ-Node A ויסתיים ב-Node E. האלגוריתם משתמש בשני תורים, כלומר QUEUE1 ו-QUEUE2. QUEUE1 מכיל את כל הצמתים שיש לעבד, בעוד QUEUE2 מכיל את כל הצמתים שמעובדים ונמחקים מ-QUEUE1.
כעת, בואו נתחיל לבחון את הגרף החל מ-Node A.
שלב 1 - ראשית, הוסף A ל-queue1 ו-NULL ל-queue2.
כיצד לבדוק את גודל המסך של המסך
QUEUE1 = {A} QUEUE2 = {NULL} שלב 2 - כעת, מחק את צומת A מ-queue1 והוסף אותו ל-queue2. הכנס את כל השכנים של צומת A ל-queue1.
QUEUE1 = {B, D} QUEUE2 = {A} שלב 3 - כעת, מחק את צומת B מ-queue1 והוסף אותו ל-queue2. הכנס את כל השכנים של צומת B ל-queue1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} שלב 4 - כעת, מחק את צומת D מ-queue1 והוסף אותו ל-queue2. הכנס את כל השכנים של צומת D ל-queue1. השכן היחיד של צומת D הוא F מכיוון שהוא כבר הוכנס, אז הוא לא יוכנס שוב.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} שלב 5 - מחק את צומת C מ-queue1 והוסף אותו ל-queue2. הכנס את כל השכנים של צומת C ל-queue1.
קריאת java csv
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} שלב 5 - מחק את הצומת F מ-queue1 והוסף אותו ל-queue2. הכנס את כל השכנים של צומת F ל-queue1. מכיוון שכל השכנים של צומת F כבר קיימים, לא נכניס אותם שוב.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} שלב 6 - מחק את הצומת E מ-queue1. מכיוון שכל השכנים שלו כבר נוספו, אז לא נכניס אותם שוב. כעת, מבקרים בכל הצמתים, וצומת היעד E נתקל ב-queue2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} המורכבות של אלגוריתם BFS
מורכבות הזמן של BFS תלויה במבנה הנתונים המשמש לייצוג הגרף. מורכבות הזמן של אלגוריתם BFS היא O(V+E) , שכן במקרה הגרוע, אלגוריתם BFS חוקר כל צומת וקצה. בגרף, מספר הקודקודים הוא O(V), בעוד שמספר הקצוות הוא O(E).
ניתן לבטא את מורכבות החלל של BFS כ O(V) , כאשר V הוא מספר הקודקודים.
יישום אלגוריתם BFS
כעת, בואו נראה את היישום של אלגוריתם BFS ב-java.
בקוד זה, אנו משתמשים ברשימת הסמיכות כדי לייצג את הגרף שלנו. הטמעת אלגוריתם Breadth-First Search ב-Java מקל בהרבה על ההתמודדות עם רשימת הסמיכות, מכיוון שעלינו לעבור ברשימת הצמתים המצורפת לכל צומת רק לאחר שהצומת תורחק מראש (או התחלה) של התור.
בדוגמה זו, הגרף שבו אנו משתמשים כדי להדגים את הקוד ניתן כדלקמן -
import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[vertex]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>