Tässä artikkelissa käsittelemme BFS-algoritmia tietorakenteessa. Breadth-first-haku on graafin läpikulkualgoritmi, joka aloittaa graafin kulkemisen juurisolmusta ja tutkii kaikki naapurisolmut. Sitten se valitsee lähimmän solmun ja tutkii kaikki tutkimattomat solmut. Kun käytät BFS:ää läpikulkuun, mitä tahansa graafin solmua voidaan pitää juurisolmuna.
On monia tapoja kulkea kuvaajan läpi, mutta niistä BFS on yleisimmin käytetty lähestymistapa. Se on rekursiivinen algoritmi, joka etsii kaikki puun tai graafin tietorakenteen kärjet. BFS asettaa graafin jokaisen kärjen kahteen luokkaan - vierailtuihin ja vierailemattomiin. Se valitsee yhden solmun kaaviosta ja vierailee sen jälkeen kaikissa valitun solmun vieressä olevissa solmuissa.
valinta lajittele javassa
BFS-algoritmin sovellukset
Leveys-ensin-algoritmin sovellukset on annettu seuraavasti -
- BFS:ää voidaan käyttää naapuripaikkojen etsimiseen tietystä lähdesijainnista.
- Vertaisverkossa BFS-algoritmia voidaan käyttää läpikulkumenetelmänä kaikkien naapurisolmujen löytämiseksi. Useimmat torrent-asiakkaat, kuten BitTorrent, uTorrent jne., käyttävät tätä prosessia löytääkseen 'siemeniä' ja 'peersiä' verkosta.
- BFS:ää voidaan käyttää Web-indeksointiroboteissa verkkosivujen indeksien luomiseen. Se on yksi tärkeimmistä algoritmeista, joita voidaan käyttää verkkosivujen indeksointiin. Se alkaa kulkea lähdesivulta ja seuraa sivuun liittyviä linkkejä. Tässä jokaista verkkosivua pidetään kaavion solmuna.
- BFS:ää käytetään lyhimmän polun ja pienimmän virityspuun määrittämiseen.
- BFS:ää käytetään myös Cheneyn tekniikassa roskien keräämisen kopioimiseen.
- Sitä voidaan käyttää ford-Fulkersonin menetelmässä virtausverkon maksimivirtauksen laskemiseen.
Algoritmi
BFS-algoritmin vaiheet kaavion tutkimiseksi esitetään seuraavasti:
Vaihe 1: SET STATUS = 1 (valmiustila) jokaiselle G:n solmulle
Vaihe 2: Aseta aloitussolmu A jonoon ja aseta sen STATUS = 2 (odotustila)
Vaihe 3: Toista vaiheita 4 ja 5, kunnes QUEUE on tyhjä
Vaihe 4: Pura solmu N. Käsittele se ja aseta sen STATUS = 3 (käsitelty tila).
Vaihe 5: Jonoa kaikki N:n naapurit, jotka ovat valmiustilassa (jonka STATUS = 1) ja aseta
heidän TILASSA = 2
(odotustila)
[SILMUKSEN LOPPU]
Vaihe 6: POISTU
resurssien allokaatiokaavio
Esimerkki BFS-algoritmista
Ymmärretään nyt BFS-algoritmin toiminta esimerkin avulla. Alla olevassa esimerkissä on suunnattu graafi, jossa on 7 kärkeä.
Yllä olevassa kaaviossa minimipolku 'P' voidaan löytää käyttämällä BFS:ää, joka alkaa solmusta A ja päättyy solmuun E. Algoritmi käyttää kahta jonoa, nimittäin QUEUE1 ja QUEUE2. QUEUE1 sisältää kaikki käsiteltävät solmut, kun taas QUEUE2 sisältää kaikki käsitellyt ja QUEUE1:stä poistetut solmut.
Aloitetaan nyt kaavion tutkiminen solmusta A alkaen.
Vaihe 1 - Lisää ensin A jonoon1 ja NULL jonoon2.
QUEUE1 = {A} QUEUE2 = {NULL} Vaihe 2 - Poista nyt solmu A jonosta1 ja lisää se jonoon2. Lisää kaikki solmun A naapurit jonoon1.
QUEUE1 = {B, D} QUEUE2 = {A} Vaihe 3 - Poista nyt solmu B jonosta1 ja lisää se jonoon2. Lisää kaikki solmun B naapurit jonoon1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Vaihe 4 - Poista nyt solmu D jonosta1 ja lisää se jonoon2. Lisää kaikki solmun D naapurit jonoon1. Solmun D ainoa naapuri on F, koska se on jo lisätty, joten sitä ei lisätä uudelleen.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Vaihe 5 - Poista solmu C jonosta 1 ja lisää se jonoon2. Lisää kaikki solmun C naapurit jonoon1.
linux kuinka nimetä hakemisto uudelleen
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Vaihe 5 - Poista solmu F jonosta1 ja lisää se jonoon2. Lisää kaikki solmun F naapurit jonoon1. Koska kaikki solmun F naapurit ovat jo läsnä, emme lisää niitä uudelleen.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Vaihe 6 - Poista solmu E jonosta1. Koska kaikki sen naapurit on jo lisätty, emme lisää niitä uudelleen. Nyt kaikissa solmuissa käydään ja kohdesolmu E törmätään jonoon2.
kielet c
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} BFS-algoritmin monimutkaisuus
BFS:n aikamonimutkaisuus riippuu kaavion esittämiseen käytetystä tietorakenteesta. BFS-algoritmin aikamonimutkaisuus on O(V+E) , koska pahimmassa tapauksessa BFS-algoritmi tutkii jokaisen solmun ja reunan. Graafissa kärkien lukumäärä on O(V), kun taas reunojen lukumäärä on O(E).
BFS:n avaruuden monimutkaisuus voidaan ilmaista seuraavasti O(V) , jossa V on pisteiden lukumäärä.
BFS-algoritmin toteutus
Katsotaanpa nyt BFS-algoritmin toteutusta javassa.
Tässä koodissa käytämme viereisyysluetteloa kuvaamaan kaavioamme. Breadth-First Search -algoritmin toteuttaminen Javassa helpottaa vierekkäisyysluettelon käsittelyä, koska meidän tarvitsee vain käydä läpi kuhunkin solmuun liitettyjen solmujen luettelon, kun solmu on purettu jonosta jonon päähän (tai alkuun).
Tässä esimerkissä kaavio, jota käytämme koodin osoittamiseen, on annettu seuraavasti -
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;>