logo

TechCodeview

BFS-algoritme i Java

Hva er BFS?

Breadth-First Search (BFS) er basert på å krysse noder ved å legge til naboene til hver node til traverseringskøen fra rotnoden. BFS for en graf er lik den for et tre, med unntak av at grafer kan ha sykluser. I motsetning til dybde-først-søk, undersøkes alle nabonoder på en gitt dybde før man går videre til neste nivå.

skjær java

BFS-algoritme

Følgende er trinnene som er involvert i å bruke bredde-først-søk for å utforske en graf:

  1. Ta dataene for grafens tilgrensningsmatrise eller tilgrensningsliste.
  2. Opprett en kø og fyll den med varer.
  3. Aktiver rotnoden (som betyr at få rotnoden i begynnelsen av køen).
  4. Sett køens hode (eller det første elementet) ut av køen, og still deretter alle køens nærliggende noder fra venstre mot høyre. Bare sett hodet ut av kø og gjenoppta operasjonen hvis en node ikke har noder i nærheten som må undersøkes. (Merk: Hvis det dukker opp en nabo som tidligere har blitt undersøkt eller står i køen, ikke sett den i kø, i stedet hopp over den.)
  5. Fortsett på denne måten til køen er tom.

BFS-applikasjoner

På grunn av algoritmens fleksibilitet er Breadth-First Search ganske nyttig i den virkelige verden. Dette er noen av dem:

  1. I et peer-to-peer-nettverk oppdages peer-noder. De fleste torrentklienter, som BitTorrent, uTorrent og qBittorent, bruker denne prosessen for å finne 'frø' og 'peers' i nettverket.
  2. Indeksen er bygget ved hjelp av graftraversalteknikker i webcrawling. Prosedyren starter med kildesiden som rotnoden og jobber seg ned til alle sekundære sider som er koblet til kildesiden (og denne prosessen fortsetter). På grunn av den reduserte dybden til rekursjonstreet, har Breadth-First Search en iboende fordel her.
  3. Bruk av GPS-navigasjonssystemer som bruker GPS, gjør et søk i bredden for å finne steder i nærheten.
  4. Cheneys teknikk, som bruker konseptet bredde-først søk, brukes til å samle søppel.

Eksempel BFS Traversal

For å komme i gang, la oss se på et enkelt eksempel. Vi starter med 0 som rotnoden og jobber oss nedover grafen.

BFS-algoritme i Java

Trinn 1: Kø(0)

Kø

0

Steg 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4)

Kø

1 3 4

Trinn 3: Dequeue(1), Enqueue(2)

Kø

3 4 2

Trinn 4: Dequeue(3), Enqueue(5). Vi vil ikke legge til 1 i køen igjen fordi 0 allerede er utforsket.

Kø

4 2 5

Trinn 5: Dekø(4)

Kø

2 5

Trinn 6: Dekø(2)

Kø

fjær og fjær mvc
5

Trinn 7: Dekø(5)

Kø

Køen er tom nå, så vi stopper prosessen.

Breadth-First Search Java-program

Det er flere måter å håndtere koden på. Vi vil for det meste diskutere trinnene som er involvert i implementering av et bredde-først-søk i Java. En tilgrensningsliste eller en tilgrensningsmatrise kan brukes til å lagre grafer; begge metodene er akseptable. Tilstøtningslisten vil bli brukt til å representere grafen vår i koden vår. Når du implementerer Breadth-First Search-algoritmen i Java, er det mye lettere å håndtere tilgrensningslisten siden vi bare trenger å reise gjennom listen over noder knyttet til hver node når noden er satt ut av køen fra hodet (eller starten) av kø.

Grafen som brukes til å demonstrere koden vil være identisk med den som ble brukt i det forrige eksempelet.

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;>