Mélység első keresés: DFS grafikon áttekintési útmutató 6 Leetcode példával

Megoldott már valódi labirintust? Az a megközelítés, amelyet a legtöbben a labirintus megoldása során követünk, az az, hogy egy ösvényen haladunk, amíg el nem érünk egy zsákutcában, majd visszalépünk és visszavezetjük lépéseinket, hogy újabb lehetséges utat találjunk.

Pontosan ez a mélység-első keresés (DFS) hasonlata. Ez egy népszerű gráf-bejárási algoritmus, amely a gyökércsomópontnál kezdődik, és amennyire csak tud, lefelé halad egy adott ágon, majd visszalép, amíg újabb felfedezetlen utat talál a felfedezéshez. Ezt a megközelítést addig folytatjuk, amíg a grafikon összes csomópontját meg nem tekintjük.

A mai oktatóanyagban egy DFS mintát fogunk felfedezni, amelyet a következő Tech Giant Interjúval kapcsolatos néhány fontos fa és grafikon kérdésének megoldására használunk! Megoldunk néhány közepes és kemény Leetcode problémát ugyanazon közös technikával.

Szóval, kezdjük, ugye?

Végrehajtás

Mivel a DFS rekurzív jellegű, verem segítségével valósítható meg.

DFS varázslat:

  1. Tegyen egy csomópontot a veremhez
  2. Pop a csomópont
  3. Keresse meg az eltávolított csomópont nem látogatott szomszédait, és nyomja őket egymásra
  4. Ismételje meg az 1., 2. és 3. lépést, amíg a verem nem üres

Grafikonjárások

Általánosságban elmondható, hogy a bináris fáknak 3 alapvető DFS bejárása van:

  1. Előrendelés: Gyökér, Bal, Jobb VAGY Gyökér, Jobb, Bal
  2. Utánrendelés: Bal, Jobb, Gyökér VAGY Jobb, Bal, Gyökér
  3. Sorrendben: Bal, Gyökér, Jobb VAGY Jobb, Gyökér, Bal

144. Bináris fa előrendelése: nehézség: közepes

Ennek a kérdésnek a megoldásához mindössze annyit kell tennünk, hogy egyszerűen felidézzük a varázsigét. Értsük meg nagyon jól a szimulációt, mivel ez az alapvető sablon, amelyet a többi probléma megoldására használunk.

Eleinte a gyökércsomópontot toljuk a verembe. Amíg a verem nem üres, bedugjuk, és a jobb és bal gyermekét belökjük a verembe.

A gyökércsomópont felbukkanásakor azonnal felvesszük az eredménylistánkba. Így az eredménylista első eleme a gyökér (innen a név, Pre-order).

A veremből következő következő elem a verem legfelső eleme lesz: a gyökércsomó bal gyermeke. A folyamat hasonló módon folytatódik mindaddig, amíg az egész gráfot be nem tették, és a bináris fa összes csomópontértéke be nem került az eredményül kapott listába.

145. Bináris fa postorder utaztatás (nehézség: nehéz)

Az előrendelés bejárása gyökér-bal-jobb , és az utólagos sorrend jobb-bal-gyökér . Ez azt jelenti, hogy a megrendelés utáni áthaladás pontosan az előrendelés bejárásának fordítottja.

Tehát az egyik megoldás, ami most eszünkbe juthat, egyszerűen megfordítja az előrendelés előtti bejárás tömbjét. De gondolj bele - ennek O (n) időbeli bonyolultságába kerülne a megfordítása.

Okosabb megoldás az előrendelés bejárásának pontos kódjának másolása és beillesztése, de az eredményt minden egyes iterációnál a csatolt lista tetejére kell tenni (0. index). Állandó időbe telik, amíg egy elem hozzáadódik a csatolt lista fejéhez. Hűvös, igaz?

94. Bináris fa bejárása (nehézség: közepes)

A probléma megoldásának megközelítése hasonló a korábbi problémákhoz. De itt mindent meglátogatunk egy csomópont bal oldalán, kinyomtatjuk a csomópontot, majd meglátogatunk mindent a csomópont jobb oldalán.

323. Csatlakoztatott alkatrészek száma egy irányítatlan grafikonban

(Nehézség: Közepes)

Itt az a megközelítésünk, hogy létrehozzunk egy ans nevű változót, amely tárolja a csatlakoztatott alkatrészek számát.

Először az összes csúcsot inicializáljuk látogatatlannak. Egy csomópontból indulunk ki, és miközben az adott csomóponton DFS-t hajtunk végre (természetesen a varázslatunk segítségével), akkor a hozzá kapcsolódó összes csomópontot meglátogatottként jelöli meg. Az ans értéke 1-gyel növekszik.

 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!