streamalism.org

1. Prehľad

V tomto tutoriáli sa pozrieme na hľadanie hĺbky v Jave.

Vyhľadávanie do hĺbky (DFS) je algoritmus prechodu používaný pre dátové štruktúry stromov aj grafov. Hĺbka prvá pred prechodom na preskúmanie inej vetvy sa vyhľadávanie prehĺbi v každej vetve.

V ďalších častiach sa najskôr pozrieme na implementáciu stromu a potom grafu.

Ak sa chcete dozvedieť, ako implementovať tieto štruktúry v Jave, pozrite si naše predchádzajúce výukové programy o binárnych stromoch a grafoch.

2. Vyhľadávanie podľa hĺbky stromu

Existujú tri rôzne príkazy na prechádzanie stromom pomocou DFS:

1. Predobjednávka Traversal
2. Traverz
3. Postorder Traversal

2.1. Predobjednávka Traversal

Pri predobjednávaní prechádzame najskôr koreňom, potom ľavým a pravým podstromom.

Môžeme jednoducho implementovať preorder traversal pomocou rekurzie:

• Navštívte prúd uzol
• Traverz vľavo podstrom
• Traverz správny podstrom

public void traversePreOrder (uzol uzla) {if (uzol! = null) {návšteva (uzol.hodnota); traversePreOrder (node.left); traversePreOrder (node.right); }}

Môžeme tiež implementovať predobjednávkový prechod bez rekurzie.

Na implementáciu iteračného predobjednávania budeme potrebovať a Stoh, a my prejdeme týmito krokmi:

• Tam koreň v našej spripináčik
• Zatiaľ čo stoh nie je prázdny
  • Pop prúd uzol
  • Navštívte prúd uzol
  • Tam správny potom dieťa vľavo dieťa do stoh

public void traversePreOrderWithoutRecursion () {Stack stack = new Stack (); Prúd uzla = root; stack.push (root); while (! stack.isEmpty ()) {current = stack.pop (); návšteva (current.value); if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}

2.2. Traverz

Pri prechode inorder, prechádzame najskôr ľavým podstromom, potom koreňom, potom nakoniec pravým podstromom.

Inorder traversal pre binárny vyhľadávací strom znamená prechádzanie uzlov v narastajúcom poradí podľa ich hodnôt.

Inorder traversal môžeme jednoducho implementovať pomocou rekurzie:

public void traverseInOrder (uzol uzla) {if (uzol! = null) {traverseInOrder (node.left); návšteva (node.value); traverseInOrder (node.right); }}

Môžeme tiež implementovať radový prechod bez rekurzie, tiež:

• Tam koreň uzol do spripináčik
• Zatiaľ čo spripináčik nie je prázdny
  • Neprestavaj tlačiť vľavo dieťa na stoh, kým sa nedostaneme prúd dieťa najviac vľavo od uzla
  • Navštívte prúd uzol
  • Tam správny dieťa na stoh

public void traverseInOrderWithoutRecursion () {Stack stack = new Stack (); Prúd uzla = root; stack.push (root); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (aktuálny); } aktualne = stack.pop (); návšteva (current.value); if (current.right! = null) {current = current.right; stack.push (aktuálny); }}}

2.3. Postorder Traversal

Nakoniec, pri prechode po poradí, prechádzame ľavým a pravým podstromom predtým, ako prechádzame koreňom.

Môžeme nasledovať svoje predchádzajúce rekurzívne riešenie:

public void traversePostOrder (uzol uzla) {if (uzol! = null) {traversePostOrder (node.left); traversePostOrder (node.right); návšteva (node.value); }}

Alebo môžeme tiež implementovať prechod po poradí bez rekurzie:

• Tam koreň uzol v spripináčik
• Zatiaľ čo spripináčik nie je prázdny
  • Skontrolujte, či sme už prešli ľavým a pravým podstromom
  • Ak nie, tak zatlačte správny dieťa a vľavo dieťa na stoh

public void traversePostOrderWithoutRecursion () {Stack stack = new Stack (); Uzol prev = root; Prúd uzla = root; stack.push (root); 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) {current = stack.pop (); návšteva (current.value); prev = prúd; } else {if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}}

3. Vyhľadávanie podľa hĺbky grafu

Hlavný rozdiel medzi grafmi a stromami je v tom grafy môžu obsahovať cykly.

Aby sme sa vyhli cyklickému vyhľadávaniu, označíme si každý uzol, keď ho navštívime.

Uvidíme dve implementácie pre graf DFS, s rekurziou a bez rekurzie.

3.1. Graf DFS s rekurziou

Najprv začnime jednoduchou rekurziou:

• Začneme od daného uzla
• Marka prúd uzol ako navštívený
• Navštívte prúd uzol
• Prejdite neviditeľnými susednými vrcholmi

public void dfs (int start) {boolean [] isVisited = new boolean [adjVertices.size ()]; dfsRecursive (start, isVisited); } private void dfsRecursive (int current, boolean [] isVisited) {isVisited [current] = true; návšteva (aktuálna); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. Graf DFS bez rekurzie

Môžeme tiež implementovať graf DFS bez rekurzie. Použijeme jednoducho a Stoh:

• Začneme od daného uzla
• Tam začať uzol do stoh
• Zatiaľ čo Stoh nie prázdny
  • Marka prúd uzol ako navštívený
  • Navštívte prúd uzol
  • Zatlačte nenavštívené susedné vrcholy

public void dfsWithoutRecursion (int start) {Stack stack = new Stack (); boolean [] isVisited = nový boolean [adjVertices.size ()]; stack.push (štart); while (! stack.isEmpty ()) {int current = stack.pop (); isVisited [current] = true; návšteva (aktuálna); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. Topologické triedenie

Existuje veľa aplikácií na vyhľadávanie podľa hĺbky grafu. Jednou zo slávnych aplikácií pre DFS je topologické triedenie.

Topologické triedenie pre smerovaný graf je lineárne usporiadanie jeho vrcholov tak, aby pre každú hranu bol zdrojový uzol pred cieľom.

Aby sme sa topologicky zoradili, budeme potrebovať jednoduchý doplnok k DFS, ktorý sme práve implementovali:

• Navštívené vrcholy musíme udržiavať v zásobníku, pretože topologické triedenie predstavuje navštívené vrcholy v opačnom poradí
• Navštívený uzol tlačíme do zásobníka až po prekonaní všetkých jeho susedov

public List topologicalSort (int start) {LinkedList result = new LinkedList (); boolean [] isVisited = nový boolean [adjVertices.size ()]; topologicalSortRecursive (start, isVisited, result); návratový výsledok; } private void topologicalSortRecursive (int current, boolean [] isVisited, LinkedList result) {isVisited [current] = true; for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } result.addFirst (aktualne); }

4. Záver

V tomto článku sme diskutovali o hĺbkovom hľadaní dátových štruktúr stromov a grafov.

Celý zdrojový kód je k dispozícii na GitHub.