Hvad er BFS?
Breadth-First Search (BFS) er baseret på at krydse noder ved at føje naboerne til hver knude til gennemkøen startende fra rodknuden. BFS for en graf ligner den for et træ, med den undtagelse, at grafer kan have cyklusser. I modsætning til dybde-først-søgning, undersøges alle naboknudepunkter i en given dybde, før de fortsætter til næste niveau.
css-justeringsbilleder
BFS algoritme
Følgende er de trin, der er involveret i at bruge bredde-først-søgning til at udforske en graf:
- Tag dataene for grafens tilstødende matrix eller tilgrænsende liste.
- Opret en kø og fyld den med varer.
- Aktiver rodnoden (hvilket betyder, at få rodnoden i begyndelsen af køen).
- Sæt køens hoved (eller indledende element) ud af køen, og sæt derefter alle køens nærliggende noder i kø fra venstre mod højre. Du skal blot sætte hovedet i kø og genoptage operationen, hvis en node ikke har nogen nærliggende noder, der skal undersøges. (Bemærk: Hvis en nabo dukker op, som tidligere er blevet undersøgt eller står i køen, skal du ikke stille den i kø, i stedet springe den over.)
- Fortsæt på denne måde, indtil køen er tom.
BFS applikationer
På grund af algoritmens fleksibilitet er Breadth-First Search ret nyttig i den virkelige verden. Disse er nogle af dem:
- I et peer-to-peer-netværk opdages peer-noder. De fleste torrent-klienter, såsom BitTorrent, uTorrent og qBittorent, anvender denne proces til at finde 'frø' og 'peers' i netværket.
- Indekset er bygget ved hjælp af graftraversalteknikker i webcrawling. Proceduren starter med kildesiden som rodknudepunktet og arbejder sig ned til alle sekundære sider, der er linket til kildesiden (og denne proces fortsætter). På grund af den reducerede dybde af rekursionstræet har Breadth-First Search en iboende fordel her.
- Brugen af GPS-navigationssystemer, der bruger GPS'en, udfører en bred-første søgning for at lokalisere nærliggende steder.
- Cheneys teknik, som anvender konceptet bredde-først søgning, bruges til at indsamle skrald.
Eksempel BFS Traversal
For at komme i gang, lad os se på et simpelt eksempel. Vi starter med 0 som rodknudepunktet og arbejder os ned i grafen.
Trin 1: Kø(0)
Kø
| 0 |
Trin 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4)
Kø
| 1 | 3 | 4 |
Trin 3: Dequeue(1), Enqueue(2)
Kø
| 3 | 4 | 2 |
Trin 4: Dequeue(3), Enqueue(5). Vi tilføjer ikke 1 til køen igen, fordi 0 allerede er blevet udforsket.
Kø
| 4 | 2 | 5 |
Trin 5: Udsæt kø (4)
Kø
| 2 | 5 |
Trin 6: Udsæt kø (2)
Kø
vælg som
| 5 |
Trin 7: Udsæt kø (5)
Kø
Køen er tom nu, så vi stopper processen.
Breadth-First Search Java-program
Der er flere tilgange til at håndtere koden. Vi vil for det meste diskutere de trin, der er involveret i implementeringen af en bred første søgning i Java. En tilgrænsende liste eller en tilgrænsende matrix kan bruges til at gemme grafer; begge metoder er acceptable. Nærhedslisten vil blive brugt til at repræsentere vores graf i vores kode. Når du implementerer Breadth-First Search-algoritmen i Java, er det meget nemmere at håndtere nabolisten, da vi kun skal rejse gennem listen over noder knyttet til hver node, når noden er sat ud af køen fra hovedet (eller starten) af kø.
Grafen, der bruges til at demonstrere koden, vil være identisk med den, der blev brugt i det foregående eksempel.
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; 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[node]; 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(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>