Široki algoritam pretraživanja na Javi

1. Pregled

U ovom uputstvu naučit ćemo o algoritmu pretraživanja širine prvo, koji nam omogućuje traženje čvora na drvetu ili grafu putujući kroz njihove čvorove prvo u širinu, a ne u dubinu.

Prvo ćemo proći kroz malo teorije o ovom algoritmu za drveće i grafikone. Nakon toga, zaronit ćemo u implementacije algoritama u Javi. Napokon ćemo pokriti njihovu vremensku složenost.

2. Algoritam pretraživanja širine i širine

Osnovni pristup algoritma za pretraživanje najšire širine (BFS) je traženje čvora u strukturi stabla ili grafa istraživanjem susjeda prije djece.

Prvo ćemo vidjeti kako ovaj algoritam radi za stabla. Nakon toga prilagodit ćemo ga grafikonima koji imaju specifična ograničenja da ponekad sadrže cikluse. Na kraju ćemo razgovarati o izvedbi ovog algoritma.

2.1. Drveće

Ideja BFS algoritma za drveće je da održavati red čvorova koji će osigurati redoslijed prelaska. Na početku algoritma, red sadrži samo korijenski čvor. Ponavljat ćemo ove korake sve dok red još sadrži jedan ili više čvorova:

  • Otvorite prvi čvor iz reda
  • Ako je taj čvor onaj koji tražimo, tada je pretraživanje završeno
  • Inače, dodajte podređene dijelove ovog čvora na kraj reda i ponovite korake

Prestanak izvršenja osiguran je odsutnošću ciklusa. Kako upravljati ciklusima, vidjet ćemo u sljedećem odjeljku.

2.2. Grafovi

U slučaju grafova, moramo razmišljati o mogućim ciklusima u strukturi. Ako prethodni algoritam jednostavno primijenimo na graf s ciklusom, on će se zauvijek petljati. Stoga, morat ćemo zadržati zbirku posjećenih čvorova i osigurati da ih ne posjetimo dva puta:

  • Otvorite prvi čvor iz reda
  • Provjerite je li čvor već posjećen, ako jeste, preskočite ga
  • Ako je taj čvor onaj koji tražimo, tada je pretraživanje završeno
  • Inače ga dodajte posjetljenim čvorovima
  • Dodajte djecu ovog čvora u red i ponovite ove korake

3. Implementacija u Javi

Sad kad je teorija obrađena, uđimo u šifru i primijenimo ove algoritme na Javi!

3.1. Drveće

Prvo ćemo implementirati algoritam stabla. Dizajnirajmo svoje Drvo razred koji se sastoji od vrijednosti i djece predstavljene popisom drugih Drvos:

stablo javne klase {privatna T vrijednost; privatni Popis djeca; privatno stablo (vrijednost T) {this.value = vrijednost; this.children = novi ArrayList (); } javno statično stablo (vrijednost T) {return new Tree (vrijednost); } javno stablo addChild (vrijednost T) {stablo newChild = novo stablo (vrijednost); kids.add (newChild); povratak newChild; }}

Da bi se izbjeglo stvaranje ciklusa, djecu kreira sam razred na temelju zadane vrijednosti.

Nakon toga, pružimo a traži() metoda:

javni statički Izborno traži (vrijednost T, korijen stabla) {// ...}

Kao što smo ranije spomenuli, algoritam BFS koristi red za prelazak čvorova. Prije svega dodajemo svoje korijen čvor u ovaj red:

Red red čekanja = novi ArrayDeque (); queue.add (root);

Zatim moramo petljati dok red nije prazan i svaki put kad izvadimo čvor iz reda:

while (! queue.isEmpty ()) {Stablo currentNode = queue.remove (); }

Ako je taj čvor onaj kojeg tražimo, vratit ćemo ga, u protivnom dodamo njegovu djecu u red čekanja:

if (currentNode.getValue (). equals (value)) {return Opcionalno.of (currentNode); } else {queue.addAll (currentNode.getChildren ()); }

Napokon, ako smo posjetili sve čvorove, a da nismo pronašli onoga kojeg tražimo, vratit ćemo prazan rezultat:

return Optional.empty ();

Zamislimo sada primjer strukture stabla:

Što se prevodi u Java kôd:

Korijen stabla = Tree.of (10); Root rootFirstChild = root.addChild (2); Dubina stablaMostChild = rootFirstChild.addChild (3); Root rootSecondChild = root.addChild (4);

Zatim, ako tražimo vrijednost 4, očekujemo da algoritam pređe čvorove sa vrijednostima 10, 2 i 4, tim redoslijedom:

BreadthFirstSearchAlgorithm.search (4, korijen)

To možemo provjeriti bilježenjem vrijednosti posjećenih čvorova:

[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Posjećeni čvor s vrijednošću: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgoritam - Posjećeni čvor s vrijednošću: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with 4: Visited node

3.2. Grafovi

Time je zaključen slučaj drveća. Pogledajmo sada kako se nositi s grafikonima. Suprotno stablima, grafovi mogu sadržavati cikluse. To znači, kao što smo vidjeli u prethodnom odjeljku, moramo se sjetiti čvorova koje smo posjetili kako bismo izbjegli beskonačnu petlju. Vidjet ćemo za trenutak kako ažurirati algoritam da razmotri ovaj problem, ali prvo, definirajmo našu strukturu grafa:

public class Node {privatna T vrijednost; privatni Set Komšije; javni čvor (vrijednost T) {this.value = vrijednost; this.neighbors = novi HashSet (); } javna void veza (čvor čvora) {if (ovaj == čvor) baca novi IllegalArgumentException ("Čvor ne može povezati sam sa sobom"); this.neighbors.add (čvor); node.neighbors.add (this); }}

Sada možemo vidjeti da, suprotno drveću, možemo slobodno povezati čvor s drugim, dajući nam mogućnost stvaranja ciklusa. Iznimka je samo što se čvor ne može povezati sam sa sobom.

Također je vrijedno napomenuti da s ovom predstavom nema korijenskog čvora. To nije problem, jer smo također uspostavili dvosmjerne veze između čvorova. To znači da ćemo moći pretraživati ​​grafikon počevši od bilo kojeg čvora.

Prije svega, ponovno upotrijebimo algoritam odozgo, prilagođen novoj strukturi:

javni statički Izborno traži (vrijednost T, početak čvora) {Redoslijed red čekanja = novi ArrayDeque (); queue.add (start); Node currentNode; while (! queue.isEmpty ()) {currentNode = queue.remove (); if (currentNode.getValue (). equals (value)) {return Opcionalno.of (currentNode); } else {queue.addAll (currentNode.getNeighbors ()); }} return Optional.empty (); }

Ne možemo pokretati algoritam ovako, ili će ga bilo koji ciklus učiniti vječnim. Dakle, moramo dodati upute za brigu o već posjećenim čvorovima:

while (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Posjećeni čvor s vrijednošću: {}", currentNode.getValue ()); if (currentNode.getValue (). equals (value)) {return Opcionalno.of (currentNode); } else {većVisited.add (currentNode); queue.addAll (currentNode.getNeighbors ()); queue.removeAll (većPosećeno); }} return Optional.empty ();

Kao što vidimo, prvo inicijaliziramo a Postavi koji će sadržavati posjećene čvorove.

Postavi alreadyVisited = novi HashSet ();

Zatim, kada usporedba vrijednosti ne uspije, dodamo čvor posjećenim:

alreadyVisited.add (currentNode);

Konačno, nakon dodavanja susjeda čvora u red, uklanjamo iz njega već posjećene čvorove (što je alternativni način provjere prisutnosti trenutnog čvora u tom skupu):

queue.removeAll (većPosećeno);

Na taj način osiguravamo da algoritam ne padne u beskonačnu petlju.

Pogledajmo kako to funkcionira na primjeru. Prije svega, definirat ćemo graf s ciklusom:

I isto u Java kodu:

Početak čvora = novi čvor (10); Čvor firstNeighbor = novi čvor (2); start.connect (firstNeighbor); Čvor firstNeighborNeighbor = novi čvor (3); firstNeighbor.connect (firstNeighborNeighbor); firstNeighborNeighbor.connect (start); Čvor secondNeighbor = novi čvor (4); start.connect (secondNeighbor);

Recimo opet da želimo tražiti vrijednost 4. Budući da nema korijenskog čvora, možemo započeti pretragu s bilo kojim čvorom koji želimo, a mi ćemo odabrati firstNeighborNeighbor:

BreadthFirstSearchAlgorithm.search (4, firstNeighborNeighbor);

Ponovno ćemo dodati zapisnik da vidimo koji su čvorovi posjećeni i očekujemo da budu 3, 2, 10 i 4, samo jednom svaki tim redoslijedom:

[main] INFO cbabBreadthFirstSearchAlgorithm - Posjećeni čvor s vrijednošću: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Posjećeni čvor s vrijednošću: 2 [main] INFO cbabBreadthFirstSearchAlgoritam - Posjećeni čvor s vrijednošću: 10 [main] INadl cf s : 4

3.3. Složenost

Sad kad smo pokrili oba algoritma u Javi, razgovarajmo o njihovoj vremenskoj složenosti. Upotrijebit ćemo oznaku Big-O da bismo ih izrazili.

Počnimo s algoritmom stabla. Čvor u red dodaje najviše jednom, stoga ga posjećuje i najviše jednom. Dakle, ako n je broj čvorova u stablu, vremenska složenost algoritma će biti Na).

Sada su, što se tiče algoritma grafova, stvari malo složenije. Proći ćemo svaki čvor najviše jednom, ali za to ćemo se poslužiti operacijama linearne složenosti kao što je Dodaj Sve() i ukloniti sve().

Razmotrimo n broj čvorova i c broj veza grafa. Tada bismo, u najgorem slučaju (jer nije pronađen čvor), mogli koristiti Dodaj Sve() i ukloniti sve() metode za dodavanje i uklanjanje čvorova do broja veza, što nam daje O (c) složenost za ove operacije. Dakle, pod uvjetom da c> n, složenost cjelokupnog algoritma bit će O (c). Inače će biti Na). To se općenito primjećuje O (n + c), što se može protumačiti kao složenost ovisno o najvećem broju između n i c.

Zašto nismo imali ovaj problem pri pretraživanju stabla? Budući da je broj veza u stablu ograničen brojem čvorova. Broj veza u stablu od n čvorovi je n - 1.

4. Zaključak

U ovom smo članku saznali o algoritmu pretraživanja širine prva i kako ga implementirati u Javu.

Nakon prolaska kroz malo teorije, vidjeli smo Java implementacije algoritma i razgovarali o njegovoj složenosti.

Kao i obično, kod je dostupan na GitHub-u.