TechCodeview

En aquest article, parlarem de l'algorisme BFS a l'estructura de dades. La cerca en amplitud és un algorisme de recorregut de gràfics que comença a recórrer el gràfic des del node arrel i explora tots els nodes veïns. A continuació, selecciona el node més proper i explora tots els nodes inexplorats. Mentre s'utilitza BFS per a la travessa, qualsevol node del gràfic es pot considerar com el node arrel.

Hi ha moltes maneres de recórrer el gràfic, però entre elles, BFS és l'enfocament més utilitzat. És un algorisme recursiu per cercar tots els vèrtexs d'una estructura de dades d'arbre o gràfic. BFS classifica cada vèrtex del gràfic en dues categories: visitat i no visitat. Selecciona un sol node en un gràfic i, després d'això, visita tots els nodes adjacents al node seleccionat.

Aplicacions de l'algorisme BFS

Les aplicacions de l'algoritme d'amplada primer es donen de la següent manera:

• BFS es pot utilitzar per trobar les ubicacions veïnes des d'una ubicació d'origen determinada.
• En una xarxa peer-to-peer, l'algorisme BFS es pot utilitzar com a mètode de recorregut per trobar tots els nodes veïns. La majoria de clients de torrent, com BitTorrent, uTorrent, etc. utilitzen aquest procés per trobar 'llavors' i 'peers' a la xarxa.
• BFS es pot utilitzar en rastrejadors web per crear índexs de pàgines web. És un dels principals algorismes que es poden utilitzar per indexar pàgines web. Comença a recórrer des de la pàgina d'origen i segueix els enllaços associats a la pàgina. Aquí, cada pàgina web es considera com un node del gràfic.
• BFS s'utilitza per determinar el camí més curt i l'arbre d'abast mínim.
• BFS també s'utilitza en la tècnica de Cheney per duplicar la recollida d'escombraries.
• Es pot utilitzar en el mètode Ford-Fulkerson per calcular el cabal màxim en una xarxa de flux.

Algorisme

Els passos implicats en l'algorisme BFS per explorar un gràfic es donen de la següent manera:

Pas 1: SET STATUS = 1 (estat preparat) per a cada node de G

Pas 2: Posa a la cua el node inicial A i defineix el seu STATUS = 2 (estat d'espera)

Pas 3: Repetiu els passos 4 i 5 fins que QUEUE estigui buida

conté en cadena

Pas 4: Treu la cua d'un node N. Processa'l i defineix el seu STATUS = 3 (estat processat).

Pas 5: Col·loqueu a la cua tots els veïns de N que es troben en l'estat llest (l'estat dels quals = 1) i establiu

el seu STATUS = 2

(estat d'espera)

avantatges d'instagram per a ús personal

[FI DEL BULE]

Pas 6: SORTIR

Exemple d'algorisme BFS

Ara, anem a comprendre el funcionament de l'algorisme BFS utilitzant un exemple. En l'exemple que es mostra a continuació, hi ha un gràfic dirigit amb 7 vèrtexs.

Al gràfic anterior, es pot trobar el camí mínim 'P' utilitzant el BFS que començarà des del node A i acabarà al node E. L'algorisme utilitza dues cues, a saber, QUEUE1 i QUEUE2. QUEUE1 conté tots els nodes que s'han de processar, mentre que QUEUE2 conté tots els nodes que es processen i es suprimeixen de QUEUE1.

què és f5 al teclat

Ara, comencem a examinar el gràfic a partir del node A.

Pas 1 - Primer, afegiu A a la cua1 i NULL a la cua2.

 QUEUE1 = {A} QUEUE2 = {NULL} 

Pas 2 - Ara, suprimiu el node A de la cua1 i afegiu-lo a la cua2. Inseriu tots els veïns del node A a la cua1.

 QUEUE1 = {B, D} QUEUE2 = {A} 

Pas 3 - Ara, suprimiu el node B de la cua1 i afegiu-lo a la cua2. Inseriu tots els veïns del node B a la cua1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B} 

Pas 4 - Ara, suprimiu el node D de la cua1 i afegiu-lo a la cua2. Inseriu tots els veïns del node D a la cua1. L'únic veí del node D és F ja que ja està inserit, de manera que no es tornarà a inserir.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D} 

Pas 5 - Eliminar el node C de la cua1 i afegir-lo a la cua2. Inseriu tots els veïns del node C a la cua1.

 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} 

Pas 5 - Eliminar el node F de la cua1 i afegir-lo a la cua2. Inseriu tots els veïns del node F a la cua1. Com que tots els veïns del node F ja estan presents, no els tornarem a inserir.

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} 

Pas 6 - Eliminar el node E de la cua1. Com que ja s'han afegit tots els seus veïns, no els tornarem a inserir. Ara, es visiten tots els nodes i el node objectiu E es troba a la cua2.

 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} 

Complexitat de l'algorisme BFS

La complexitat temporal de BFS depèn de l'estructura de dades utilitzada per representar el gràfic. La complexitat temporal de l'algorisme BFS és O(V+E) , ja que en el pitjor dels casos, l'algorisme BFS explora cada node i vora. En un gràfic, el nombre de vèrtexs és O(V), mentre que el nombre d'arestes és O(E).

La complexitat espacial de BFS es pot expressar com O(V) , on V és el nombre de vèrtexs.

Implementació de l'algorisme BFS

Ara, vegem la implementació de l'algorisme BFS a Java.

porció de matriu java

En aquest codi, estem utilitzant la llista d'adjacència per representar el nostre gràfic. La implementació de l'algoritme de cerca Breadth-First a Java fa que sigui molt més fàcil tractar la llista d'adjacència, ja que només hem de viatjar per la llista de nodes connectats a cada node una vegada que el node es retira de la cua del capçal (o inici) de la cua.

En aquest exemple, el gràfic que estem utilitzant per demostrar el codi es dóna de la següent manera:

 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&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>