Dybde første søgning: en DFS Graph Traversal Guide med 6 Leetcode-eksempler

Har du nogensinde løst en ægte labyrint? Den tilgang, som de fleste af os tager, når vi løser en labyrint, er at vi følger en sti, indtil vi når en blindgyde, og derefter går tilbage og sporer vores skridt for at finde en anden mulig sti.

Dette er nøjagtigt analogien med Depth First Search (DFS). Det er en populær grafgennemgangsalgoritme, der starter ved rodknudepunktet og bevæger sig så langt det kan ned ad en given gren og derefter bakker, indtil den finder en anden uudforsket vej at udforske. Denne tilgang fortsættes, indtil alle noder i grafen er blevet besøgt.

I dagens tutorial vil vi opdage et DFS-mønster, der vil blive brugt til at løse nogle af de vigtige træ- og grafspørgsmål til dit næste Tech Giant Interview! Vi løser nogle Medium og Hard Leetcode-problemer ved hjælp af den samme almindelige teknik.

Så lad os komme i gang, skal vi?

Implementering

Da DFS har en rekursiv karakter, kan den implementeres ved hjælp af en stak.

DFS-magi:

  1. Skub en knude til stakken
  2. Pop noden
  3. Hent ubesøgte naboer til den fjernede knude, skub dem til stakken
  4. Gentag trin 1, 2 og 3, så længe stakken ikke er tom

Graf gennemgange

Generelt er der 3 grundlæggende DFS-gennemgange for binære træer:

  1. Forudbestilling: rod, venstre, højre ELLER rod, højre, venstre
  2. Postordre: Venstre, højre, rod ELLER højre, venstre, rod
  3. I rækkefølge: Venstre, rod, højre ELLER højre, rod, venstre

144. Traversal for binær træforudbestilling (vanskelighed: medium)

For at løse dette spørgsmål er alt, hvad vi skal gøre, blot at huske vores magiske trylleformular. Lad os forstå simuleringen rigtig godt, da dette er den grundlæggende skabelon, vi bruger til at løse resten af ​​problemerne.

Først skubber vi rodnoden ind i stakken. Mens stakken ikke er tom, springer vi den og skubber dens højre og venstre barn ind i stakken.

Når vi popper rodnoden, placerer vi den straks på vores resultatliste. Således er det første element i resultatlisten roden (deraf navnet, forudbestilling).

Det næste element, der skal poppes fra stakken, er det øverste element i stakken lige nu: det venstre barn til rodnoden. Processen fortsættes på en lignende måde, indtil hele grafen er blevet krydset, og alle nodeværdierne i det binære træ går ind i den resulterende liste.

145. Trafikovergang med binært træ (vanskelighed: hårdt)

Forudbestill traversal er root-venstre-højre , og efterbestilling er højre-venstre-rod . Dette betyder, at postorder-traversal er nøjagtigt det modsatte af pre-order-traversal.

Så en løsning, der måske kommer til at tænke på lige nu, er simpelthen at vende det resulterende udvalg af forudbestillingsgennemgang. Men tænk over det - det ville koste O (n) tidskompleksitet at vende det.

En smartere løsning er at kopiere og indsætte den nøjagtige kode for den forudbestilte traversal, men placere resultatet øverst på den sammenkædede liste (indeks 0) ved hver iteration. Det tager konstant tid at tilføje et element til hovedet på en linket liste. Sejt, ikke?

94. Traversering af binært træ (vanskelighed: medium)

Vores tilgang til at løse dette problem svarer til de tidligere problemer. Men her vil vi besøge alt på venstre side af en node, udskrive node og derefter besøge alt på højre side af node.

323. Antal tilsluttede komponenter i en ikke-dirigeret graf

(Sværhedsgrad: Medium)

Vores tilgang her er at oprette en variabel kaldet ans, der gemmer antallet af tilsluttede komponenter.

For det første initialiserer vi alle hjørner som ubesøgte. Vi starter fra en node, og mens vi udfører DFS på den node (selvfølgelig ved hjælp af vores magiske stave), vil den markere alle de noder, der er forbundet med den, som besøgt. Værdien af ans øges med 1.

 import java.util.ArrayList; import java.util.List; import java.util.Stack; public class NumberOfConnectedComponents { public static void main(String[] args){ int[][] edge = {{0,1}, {1,2},{3,4}}; int n = 5; System.out.println(connectedcount(n, edge)); } public static int connectedcount(int n, int[][] edges) { boolean[] visited = new boolean[n]; List[] adj = new List[n]; for(int i=0; i
    

200. Number of Islands (Difficulty: Medium)

This falls under a general category of problems where we have to find the number of connected components, but the details are a bit tweaked.

Instinctually, you might think that once we find a “1” we initiate a new component. We do a DFS from that cell in all 4 directions (up, down, right, left) and reach all 1’s connected to that cell. All these 1's connected to each other belong to the same group, and thus, our value of count is incremented by 1. We mark these cells of 1's as visited and move on to count other connected components.

547. Friend Circles (Difficulty: Medium)

This also follows the same concept as finding the number of connected components. In this question, we have an NxN matrix but only N friends in total. Edges are directly given via the cells so we have to traverse a row to get the neighbors for a specific "friend".

Notice that here, we use the same stack pattern as our previous problems.

That's all for today! I hope this has helped you understand DFS better and that you have enjoyed the tutorial. Please recommend this post if you think it may be useful for someone else!