streamalism.org

1. Oversikt

I denne opplæringen vil vi utforske det dybde-første søket i Java.

Dybde-første søk (DFS) er en traversalgoritme som brukes for både tre- og grafdatastrukturer. Dybden-først søk går dypt i hver gren før de går for å utforske en annen gren.

I de neste avsnittene vil vi først se på implementeringen av et tre og deretter en graf.

For å se hvordan du implementerer disse strukturene i Java, ta en titt på våre tidligere opplæringsprogrammer om Binary Tree and Graph.

2. Treddybde-første søk

Det er tre forskjellige ordrer for å krysse et tre ved hjelp av DFS:

1. Forhåndsbestilling
2. Inorder Traversal
3. Postorder Traversal

2.1. Forhåndsbestilling

I forhåndsbestilling av traversering krysser vi først roten, deretter venstre og høyre undertrær.

Vi kan rett og slett implementere preorder traversal ved hjelp av rekursjon:

• Besøk nåværende node
• Travers venstre undertreet
• Travers Ikke sant undertreet

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

Vi kan også implementere forhåndsbestilling gjennomgang uten rekursjon.

For å implementere en iterativ forhåndsbestillingstrafikk, trenger vi en Stable, og vi vil gå gjennom disse trinnene:

• Trykk rot i vår sstift
• Samtidig som stable er ikke tom
  • Pop nåværende node
  • Besøk nåværende node
  • Trykk Ikke sant barn, da venstre barn til stable

public void traversePreOrderWithoutRecursion () {Stack stack = new Stack (); Node nåværende = rot; stack.push (root); while (! stack.isEmpty ()) {current = stack.pop (); besøk (gjeldende.verdi); hvis (current.right! = null) {stack.push (current.right); } hvis (current.left! = null) {stack.push (current.left); }}}

2.2. Inorder Traversal

For inorder traversal, vi krysser venstre undertre først, deretter roten, så til slutt høyre undertre.

Inorder traversal for et binært søketre betyr å krysse nodene i økende rekkefølge av deres verdier.

Vi kan ganske enkelt implementere inorder traversal ved hjelp av rekursjon:

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

Vi kan også implementere inorder traversal uten rekursjonogså:

• Trykk rot node til sstift
• Mens sstift er ikke tom
  • Fortsett å presse venstre barnet på stable, til vi når nåværende nodens venstre barn
  • Besøk nåværende node
  • Trykk Ikke sant barnet på stable

public void traverseInOrderWithoutRecursion () {Stack stack = new Stack (); Node nåværende = rot; stack.push (root); while (! stack.isEmpty ()) {while (current.left! = null) {current = current.left; stack.push (gjeldende); } gjeldende = stack.pop (); besøk (gjeldende.verdi); hvis (current.right! = null) {current = current.right; stack.push (gjeldende); }}}

2.3. Postorder Traversal

Til slutt, i postorder traversal, vi krysser venstre og høyre undertre før vi krysser roten.

Vi kan følge vår forrige rekursiv løsning:

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

Eller vi kan også implementere postorder traversal uten rekursjon:

• Trykk rot node i sstift
• Mens sstift er ikke tom
  • Sjekk om vi allerede har krysset venstre og høyre undertreet
  • Hvis ikke så trykk Ikke sant barn og venstre barnet på stable

public void traversePostOrderWithoutRecursion () {Stack stack = new Stack (); Node prev = rot; Node nåværende = rot; stack.push (root); mens (! stack.isEmpty ()) {gjeldende = stack.peek (); boolsk hasChild = (current.left! = null || current.right! = null); boolsk isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (! hasChild || isPrevLastChild) {current = stack.pop (); besøk (gjeldende.verdi); prev = gjeldende; } annet {if (current.right! = null) {stack.push (current.right); } hvis (current.left! = null) {stack.push (current.left); }}}}

3. Graf Dybde-første søk

Hovedforskjellen mellom grafer og trær er at grafer kan inneholde sykluser.

Så for å unngå å søke i sykluser, markerer vi hver node når vi besøker den.

Vi ser to implementeringer for graf DFS, med rekursjon og uten rekursjon.

3.1. Graf DFS med rekursjon

Først, la oss starte enkelt med rekursjon:

• Vi starter fra en gitt node
• merke nåværende node som besøkt
• Besøk nåværende node
• Kryss ubesøkte tilstøtende hjørner

public void dfs (int start) {boolean [] isVisited = new boolean [adjVertices.size ()]; dfsRecursive (start, isVisited); } privat ugyldig dfsRecursive (int current, boolean [] isVisited) {isVisited [current] = true; besøk (nåværende); for (int dest: adjVertices.get (nåværende)) {if (! isVisited [dest]) dfsRecursive (dest, isVisited); }}

3.2. Graf DFS uten rekursjon

Vi kan også implementere graf DFS uten rekursjon. Vi bruker ganske enkelt en Stable:

• Vi starter fra en gitt node
• Trykk start node inn stable
• Samtidig som Stable ikke tom
  • merke nåværende node som besøkt
  • Besøk nåværende node
  • Skyv ubesøkte tilstøtende hjørner

offentlig tomrom dfsWithoutRecursion (int start) {Stack stack = new Stack (); boolsk [] isVisited = ny boolsk [adjVertices.size ()]; stack.push (start); mens (! stack.isEmpty ()) {int gjeldende = stack.pop (); isVisited [current] = true; besøk (nåværende); for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) stack.push (dest); }}}

3.4. Topologisk sortering

Det er mange applikasjoner for grafdybde-første søk. En av de berømte applikasjonene for DFS er Topological Sort.

Topologisk sortering for en rettet graf er en lineær rekkefølge av toppunktene slik at kildekoden kommer for målet for hver kant.

For å bli sortert topologisk, trenger vi et enkelt tillegg til DFS vi nettopp implementerte:

• Vi må holde de besøkte toppunktene i en bunke fordi den topologiske typen er de besøkte toppunktene i omvendt rekkefølge
• Vi skyver den besøkte noden til stabelen bare etter å ha krysset alle naboene

public List topologicalSort (int start) {LinkedList result = new LinkedList (); boolsk [] isVisited = ny boolsk [adjVertices.size ()]; topologicalSortRecursive (start, isVisited, result); returresultat; } privat ugyldig topologicalSortRecursive (int current, boolean [] isVisited, LinkedList result) {isVisited [current] = true; for (int dest: adjVertices.get (current)) {if (! isVisited [dest]) topologicalSortRecursive (dest, isVisited, result); } resultat.addFirst (nåværende); }

4. Konklusjon

I denne artikkelen diskuterte vi det dybde-første søket etter både tre- og grafdatastrukturene.

Hele kildekoden er tilgjengelig på GitHub.