Diepte eerste zoekopdracht in Java

1. Overzicht

In deze zelfstudie onderzoeken we de diepte-eerst-zoekactie in Java.

Depth-first search (DFS) is een traversal-algoritme dat wordt gebruikt voor zowel Tree- als Graph-datastructuren. De diepte eerst zoeken gaat diep in elke branch voordat je naar een andere branch gaat.

In de volgende secties bekijken we eerst de implementatie voor een boom en vervolgens een grafiek.

Bekijk onze eerdere tutorials over Binary Tree and Graph om te zien hoe u deze structuren in Java implementeert.

2. Boomdiepte-eerst zoeken

Er zijn drie verschillende volgordes voor het doorkruisen van een boom met DFS:

  1. Traversal reserveren
  2. In volgorde doorlopen
  3. Postordertraversal

2.1. Traversal reserveren

Bij pre-order traversal doorlopen we eerst de wortel, dan de linker en rechter substructuren.

We kunnen het gewoon preorder traversal implementeren met behulp van recursie:

  • Bezoek actueel knooppunt
  • Traverse links substructuur
  • Traverse Rechtsaf substructuur
public void traversePreOrder (Node node) {if (node! = null) {visit (node.value); traversePreOrder (node.left); traversePreOrder (node.right); }}

We kunnen ook pre-order traversal implementeren zonder recursie.

Om een ‚Äč‚Äčiteratieve preorder-traversal te implementeren, hebben we een Stapel, en we zullen deze stappen doorlopen:

  • Duwen wortel in onze soverstag
  • Terwijl stapel is niet leeg
    • Knal actueel knooppunt
    • Bezoek actueel knooppunt
    • Duwen Rechtsaf kind, dan links kind aan stapel
openbare ongeldige traversePreOrderWithoutRecursion () {Stack stack = new Stack (); Knoopstroom = root; stack.push (root); while (! stack.isEmpty ()) {current = stack.pop (); bezoek (huidige.waarde); if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}

2.2. In volgorde doorlopen

Voor in volgorde doorlopen, we doorlopen eerst de linker substructuur, dan de wortel, en dan tenslotte de rechter substructuur.

Doorlopen voor een binaire zoekboom betekent het doorlopen van de knooppunten in oplopende volgorde van hun waarden.

We kunnen eenvoudig in volgorde traversal implementeren met behulp van recursie:

public void traverseInOrder (Node node) {if (node! = null) {traverseInOrder (node.left); bezoek (node.value); traverseInOrder (node.right); }}

We kunnen ook implementeren in volgorde doorlopen zonder recursieook:

  • Duwen wortel knooppunt naar soverstag
  • Terwijl soverstag is niet leeg
    • Blijf duwen links kind op stapel, totdat we bereiken actueel het meest linkse kind van het knooppunt
    • Bezoek actueel knooppunt
    • Duwen Rechtsaf kind op stapel
openbare ongeldige traverseInOrderWithoutRecursion () {Stack stack = new Stack (); Knoopstroom = root; stack.push (root); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (huidig); } current = stack.pop (); bezoek (huidige.waarde); if (current.right! = null) {current = current.right; stack.push (huidig); }}}

2.3. Postorderoverschrijding

Ten slotte, in postordertraversal, we doorkruisen de linker en rechter substructuur voordat we de wortel doorlopen.

We kunnen onze vorige volgen recursieve oplossing:

public void traversePostOrder (Node node) {if (node! = null) {traversePostOrder (node.left); traversePostOrder (node.right); bezoek (node.value); }}

Of we kunnen ook postorder traversal implementeren zonder recursie:

  • Duwen wortel knooppunt in soverstag
  • Terwijl soverstag is niet leeg
    • Controleer of we de linker en rechter substructuur al hebben doorlopen
    • Zo niet, druk dan op Rechtsaf kind en links kind op stapel
openbare ongeldige traversePostOrderWithoutRecursion () {Stack stack = new Stack (); Knooppunt prev = root; Knoopstroom = 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 (); bezoek (huidige.waarde); prev = huidig; } else {if (current.right! = null) {stack.push (current.right); } if (current.left! = null) {stack.push (current.left); }}}}

3. Grafiek diepte-eerst zoeken

Het belangrijkste verschil tussen grafieken en bomen is dat grafieken kunnen cycli bevatten.

Dus om zoeken in cycli te vermijden, zullen we elk knooppunt markeren wanneer we het bezoeken.

We zullen twee implementaties zien voor grafiek-DFS, met recursie en zonder recursie.

3.1. Grafiek DFS met recursie

Laten we eerst eenvoudig beginnen met recursie:

  • We beginnen vanaf een bepaald knooppunt
  • Mark actueel knooppunt zoals bezocht
  • Bezoek actueel knooppunt
  • Doorkruis onbezochte aangrenzende hoekpunten
openbare void dfs (int start) {boolean [] isVisited = nieuwe boolean [adjVertices.size ()]; dfsRecursive (start, isVisited); } private void dfsRecursive (int current, boolean [] isVisited) {isVisited [current] = true; bezoek (huidig); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. Grafiek DFS zonder recursie

We kunnen ook grafiek-DFS implementeren zonder recursie. We gebruiken gewoon een Stapel:

  • We beginnen vanaf een bepaald knooppunt
  • Duwen begin knooppunt in stapel
  • Terwijl Stapel niet leeg
    • Mark actueel knooppunt zoals bezocht
    • Bezoek actueel knooppunt
    • Duw onbezochte aangrenzende hoekpunten
public void dfsWithoutRecursion (int start) {Stack stack = new Stack (); boolean [] isVisited = nieuwe boolean [adjVertices.size ()]; stack.push (start); while (! stack.isEmpty ()) {int current = stack.pop (); isVisited [huidig] = waar; bezoek (huidig); voor (int dest: adjVertices.get (huidig)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. Topologische sortering

Er zijn veel toepassingen voor het zoeken naar diepte eerst. Een van de bekende applicaties voor DFS is Topological Sort.

Topologische sortering voor een gerichte graaf is een lineaire ordening van zijn hoekpunten, zodat voor elke rand het bronknooppunt vóór de bestemming komt.

Om topologisch gesorteerd te worden, hebben we een eenvoudige toevoeging nodig aan de DFS die we zojuist hebben geïmplementeerd:

  • We moeten de bezochte hoekpunten in een stapel bewaren omdat de topologische sortering de bezochte hoekpunten in omgekeerde volgorde is
  • We duwen het bezochte knooppunt pas naar de stapel nadat we al zijn buren hebben doorlopen
openbare lijst topologicalSort (int start) {LinkedList resultaat = nieuwe LinkedList (); boolean [] isVisited = nieuwe boolean [adjVertices.size ()]; topologicalSortRecursive (start, isVisited, resultaat); resultaat teruggeven; } private void topologicalSortRecursive (int current, boolean [] isVisited, LinkedList resultaat) {isVisited [current] = true; for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } result.addFirst (huidig); }

4. Conclusie

In dit artikel hebben we de diepte-eerst-zoekactie voor zowel de Tree- als de Graph-datastructuur besproken.

De volledige broncode is beschikbaar op GitHub.