streamalism.org

1. Oversigt

I denne vejledning udforsker vi dybde-første søgning i Java.

Dybde-første søgning (DFS) er en traversalgoritme, der bruges til både træ- og grafdatastrukturer. Dybden-først søgning går dybt i hver gren, inden de går for at udforske en anden gren.

I de næste sektioner skal vi først se på implementeringen af ​​et træ og derefter en graf.

For at se, hvordan du implementerer disse strukturer i Java, skal du kigge på vores tidligere tutorials om binært træ og graf.

2. Trædybde-første søgning

Der er tre forskellige ordrer til at krydse et træ ved hjælp af DFS:

1. Forudbestil gennemgang
2. Inorder Traversal
3. Postorder-gennemgang

2.1. Forudbestil gennemgang

I forudbestillingskørsel krydser vi først roden, derefter venstre og højre undertrær.

Det kan vi ganske enkelt implementere preorder traversal ved hjælp af rekursion:

• Besøg nuværende knude
• Travers venstre undertræ
• Travers ret undertræ

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

Vi kan også gennemføre preorder-gennemgang uden rekursion.

For at implementere en iterativ forudbestilling gennemgang har vi brug for en Stak, og vi gennemgår disse trin:

• Skubbe rod i vores stack
• Mens stak er ikke tom
  • Pop nuværende knude
  • Besøg nuværende knude
  • Skubbe ret barn, så venstre barn til stak

public void traversePreOrderWithoutRecursion () {Stack stack = new Stack (); Node nuværende = rod; stack.push (rod); mens (! stack.isEmpty ()) {nuværende = stack.pop (); besøg (nuværende værdi); hvis (current.right! = null) {stack.push (current.right); } hvis (current.left! = null) {stack.push (current.left); }}}

2.2. Inorder Traversal

For inorder traversal, vi krydser det venstre undertræ først, derefter roden og derefter til sidst det højre undertræ.

Inorder traversal for et binært søgetræ betyder at krydse noderne i stigende rækkefølge af deres værdier.

Vi kan simpelthen implementere inorder traversal ved hjælp af rekursion:

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

Det kan vi også implementere inorder traversal uden rekursion, også:

• Skubbe rod knude til stack
• Mens stack er ikke tom
  • Bliv ved med at skubbe venstre barn på stak, indtil vi når nuværende knudens venstre barn
  • Besøg nuværende knude
  • Skubbe ret barn på stak

public void traverseInOrderWithoutRecursion () {Stack stack = new Stack (); Node nuværende = rod; stack.push (rod); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (nuværende); } nuværende = stack.pop (); besøg (nuværende værdi); hvis (current.right! = null) {current = current.right; stack.push (nuværende); }}}

2.3. Postorder gennemgang

Endelig i postorder traversal, vi krydser venstre og højre undertræ, før vi krydser roden.

Vi kan følge vores tidligere rekursiv løsning:

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

Eller vi kan også implementere postorder traversal uden rekursion:

• Skubbe rod knude i stack
• Mens stack er ikke tom
  • Kontroller, om vi allerede har krydset venstre og højre undertræ
  • Hvis ikke så skub ret barn og venstre barn på stak

public void traversePostOrderWithoutRecursion () {Stack stack = new Stack (); Node prev = rod; Node nuværende = rod; stack.push (rod); mens (! stack.isEmpty ()) {nuværende = stack.peek (); boolsk hasChild = (nuværende.venstre! = nul || nuværende.højre! = nul); boolsk isPrevLastChild = (prev == nuværende.højre || (forrige == nuværende. venstre && nuværende.højde == null)); hvis (! hasChild || isPrevLastChild) {nuværende = stack.pop (); besøg (nuværende værdi); prev = strøm; } ellers {if (current.right! = null) {stack.push (current.right); } hvis (current.left! = null) {stack.push (current.left); }}}}

3. Graf Dybde-første søgning

Den største forskel mellem grafer og træer er, at grafer kan indeholde cyklusser.

Så for at undgå at søge i cyklusser markerer vi hver node, når vi besøger den.

Vi ser to implementeringer til graf DFS med rekursion og uden rekursion.

3.1. Graf DFS med rekursion

Lad os først starte simpelt med rekursion:

• Vi starter fra en given node
• Mærke nuværende node som besøgt
• Besøg nuværende knude
• Kryds ubesøgte tilstødende hjørner

offentlig ugyldig dfs (int start) {boolsk [] isVisited = ny boolsk [adjVertices.size ()]; dfsRecursive (start, isVisited); } privat ugyldigt dfsRecursive (int nuværende, boolsk [] isVisited) {isVisited [nuværende] = sand; besøg (nuværende) for (int dest: adjVertices.get (nuværende)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. Graf DFS uden rekursion

Vi kan også implementere graf DFS uden rekursion. Vi bruger simpelthen en Stak:

• Vi starter fra en given node
• Skubbe Start knude ind i stak
• Mens Stak ikke tom
  • Mærke nuværende node som besøgt
  • Besøg nuværende knude
  • Skub ubesøgte tilstødende hjørner

public void dfsWithoutRecursion (int start) {Stack stack = new Stack (); boolsk [] isVisited = ny boolsk [adjVertices.size ()]; stack.push (start); mens (! stack.isEmpty ()) {int nuværende = stack.pop (); isVisited [nuværende] = sandt; besøg (nuværende) for (int dest: adjVertices.get (nuværende)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. Topologisk sortering

Der er mange applikationer til grafdybde-første søgning. En af de berømte applikationer til DFS er Topologisk sortering.

Topologisk sortering for en rettet graf er en lineær rækkefølge af dens hjørner, så kildeknudepunktet for hver kant kommer før destinationen.

For at blive sorteret topologisk har vi brug for en simpel tilføjelse til den DFS, vi lige har implementeret:

• Vi er nødt til at holde de besøgte hjørner i en stak, fordi den topologiske slags er de besøgte hjørner i en omvendt rækkefølge
• Vi skubber den besøgte knude til stakken kun efter at have krydset alle sine naboer

public List topologicalSort (int start) {LinkedList result = new LinkedList (); boolsk [] isVisited = ny boolsk [adjVertices.size ()]; topologicalSortRecursive (start, isVisited, result); returresultat } privat ugyldigt topologiskSortRecursive (int nuværende, boolsk [] isVisited, LinkedList resultat) {isVisited [nuværende] = sand; for (int dest: adjVertices.get (nuværende)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } resultat.addFirst (nuværende); }

4. Konklusion

I denne artikel diskuterede vi dybde-første søgning efter både træ- og graf-datastrukturer.

Den fulde kildekode er tilgængelig på GitHub.