streamalism.org

1. Pregled

U ovom ćemo uputstvu istražiti dubinsko pretraživanje na Javi.

Dubinsko pretraživanje (DFS) algoritam je prelaska koji se koristi i za podatkovne strukture stabla i grafa. Prvo dubina pretraga ide duboko u svaku granu prije nego što krenemo istraživati ​​drugu granu.

U sljedećim odjeljcima prvo ćemo pogledati implementaciju stabla, a zatim grafikona.

Da biste vidjeli kako implementirati ove strukture u Javi, pogledajte naše prethodne vodiče o Binarnom stablu i grafikonu.

2. Pretraživanje dubine stabla

Postoje tri različita naloga za prelazak stablom pomoću DFS-a:

1. Prijelaz predbilježbe
2. Unutarnja obilaznica
3. Prijelaz poštarine

2.1. Prijelaz predbilježbe

U prijelomu predbilježbe prvo prelazimo korijen, a zatim lijevo i desno podstabla.

Možemo jednostavno implementirati preorder prijelaz koristeći rekurziju:

• Posjetiti Trenutno čvor
• prijeći lijevo podstablo
• prijeći pravo podstablo

javna praznina traversePreOrder (čvor čvora) {if (čvor! = null) {visit (node.value); traversePreOrder (node.left); traversePreOrder (node.desno); }}

Također možemo implementirati preusmjeravanje predbilježbe bez rekurzije.

Da bismo proveli iterativno preusmjeravanje predbilježbe, trebat će nam Stog, i mi ćemo proći kroz ove korake:

• Gurnuti korijen u našem sljepljivost
• Dok stog nije prazna
  • Pop Trenutno čvor
  • Posjetiti Trenutno čvor
  • Gurnuti pravo dijete onda lijevo dijete da stog

javna praznina traversePreOrderWithoutRecursion () {Stack stog = novi Stack (); Struja čvora = korijen; stog.push (korijen); while (! stack.isEmpty ()) {current = stack.pop (); posjet (current.value); if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}

2.2. Unutarnja obilaznica

Za unutarnje zaobilaženje, prvo prelazimo lijevo podstablo, zatim korijen, pa na kraju desno podstablo.

Prelazak poreda za binarno stablo pretraživanja znači prelazak čvorova u rastućem redoslijedu njihovih vrijednosti.

Jednostavno možemo implementirati inorder obilaženje pomoću rekurzije:

javna praznina traverseInOrder (čvor čvora) {if (čvor! = null) {traverseInOrder (node.left); posjet (node.value); traverseInOrder (node.desno); }}

Možemo i mi provesti inorder obilazak bez rekurzije, isto:

• Gurnuti korijen čvor do sljepljivost
• Dok sljepljivost nije prazna
  • Nastavi gurati lijevo dijete na stog, dok ne stignemo Trenutno najdije dijete čvora
  • Posjetiti Trenutno čvor
  • Gurnuti pravo dijete na stog

javna praznina traverseInOrderWithoutRecursion () {Stack stog = novi Stack (); Struja čvora = korijen; stog.push (korijen); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (trenutno); } tekuće = stack.pop (); posjet (current.value); if (current.right! = null) {current = current.right; stack.push (trenutno); }}}

2.3. Prijelaz poštarine

Konačno, u prijelazu postorder, prelazimo lijevo i desno podstablo prije nego što pređemo korijen.

Možemo slijediti naše prethodne rekurzivno rješenje:

javna praznina traversePostOrder (čvor čvora) {if (čvor! = null) {traversePostOrder (node.left); traversePostOrder (node.desno); posjet (node.value); }}

Ili, također možemo provesti obilazak postorder bez rekurzije:

• Gurnuti korijen čvor u sljepljivost
• Dok sljepljivost nije prazna
  • Provjerite jesmo li već prešli lijevo i desno podstablo
  • Ako ne, onda pritisnite pravo dijete i lijevo dijete na stog

javna praznina traversePostOrderWithoutRecursion () {Stack stog = novi Stack (); Čvor prev = root; Struja čvora = korijen; stog.push (korijen); while (! stack.isEmpty ()) {current = stack.peek (); boolean hasChild = (current.left! = null || current.right! = null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (! hasChild || isPrevLastChild) {trenutno = stack.pop (); posjet (current.value); prev = trenutno; } else {if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}}

3. Pretraživanje dubine grafikona

Glavna razlika između grafova i stabala je ta grafovi mogu sadržavati cikluse.

Kako bismo izbjegli pretraživanje u ciklusima, označit ćemo svaki čvor kad ga posjetimo.

Vidjet ćemo dvije implementacije za DFS grafa, s rekurzijom i bez rekurzije.

3.1. Grafikon DFS s rekurzijom

Prvo, krenimo jednostavno s rekurzijom:

• Krenut ćemo od zadanog čvora
• Ocjena Trenutno čvor kao posjećen
• Posjetiti Trenutno čvor
• Prelazak ne posjećenih susjednih vrhova

javna void dfs (int start) {boolean [] isVisited = new boolean [adjVertices.size ()]; dfsRecursive (start, isVisited); } private void dfsRecursive (int current, boolean [] isVisited) {isVisited [current] = true; posjet (trenutni); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. Grafikon DFS bez rekurzije

Također možemo implementirati graf DFS bez rekurzije. Jednostavno ćemo koristiti Stog:

• Krenut ćemo od zadanog čvora
• Gurnuti početak čvor u stog
• Dok Stog nije prazno
  • Ocjena Trenutno čvor kao posjećen
  • Posjetiti Trenutno čvor
  • Gurajte neposjećene susjedne vrhove

javna void dfsWithoutRecursion (int start) {Stack stack = novi Stack (); boolean [] isVisited = novo boolean [adjVertices.size ()]; stack.push (start); while (! stack.isEmpty ()) {int current = stack.pop (); isVisited [current] = true; posjet (trenutni); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. Topološko sortiranje

Puno je aplikacija za pretragu dubine grafa. Jedna od poznatih aplikacija za DFS je Topološko sortiranje.

Topološko sortiranje za usmjereni graf linearno je uređenje njegovih vrhova tako da za svaki rub izvorni čvor dolazi ispred odredišta.

Da bismo se topološki sortirali, trebat će nam jednostavan dodatak DFS-u koji smo upravo implementirali:

• Posjećene vrhove moramo držati u hrpi, jer je topološka sorta posjećene vrhove obrnutim redoslijedom
• Posjećeni čvor guramo u stog tek nakon prelaska svih njegovih susjeda

javni popis topologicalSort (int start) {LinkedList rezultat = novi LinkedList (); boolean [] isVisited = novo boolean [adjVertices.size ()]; topologicalSortRecursive (početak, isVisited, rezultat); povratni rezultat; } private void topologicalSortRecursive (int current, boolean [] isVisited, LinkedList rezultat) {isVisited [current] = true; for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } result.addFirst (trenutno); }

4. Zaključak

U ovom smo članku razgovarali o dubinskom pretraživanju struktura podataka Tree i Graph.

Cjeloviti izvorni kod dostupan je na GitHubu.