A Breadth First Search (BFS) az egyik legnépszerűbb algoritmus egy fa vagy grafikon adatszerkezetének keresésére vagy áthaladására. Ebben az oktatóanyagban röviden megismerhetjük a BFS működését, és feltárhatunk egy alapmintát, amely felhasználható néhány közepes és könnyű probléma megoldására a Leetcode-ban.
Kezdjük, ugye?
Mi a Breadth First Search?
Tehát mindannyian tudjuk, hogy a gráf csúcsok és élek halmaza: G = {V, E}. A grafikonon való áthaladás azt jelenti, hogy minden csúcsot és élt pontosan egyszer , rendezett módon kell meglátogatni .
A BFS-ben a gráfot szélességenként vagy szintenként kell haladnunk. Ez azt jelenti, hogy először vízszintesen haladunk, és meglátogatjuk az aktuális réteg összes csomópontját, mielőtt továbblépnénk a következő rétegre.
Ezért, amikor felkérést kapunk valamilyen szintű sorrendbeli bejárásra, használhatjuk a BFS technikát.
A BFS-ben 1-től kezdve (a gyökércsomópont) kezdtük volna meg az utat, és meglátogattuk a gyermek 8, 5 és 2 gyermekcsomópontjait. Tároljuk őket abban a sorrendben, amelyben meglátogattuk őket. Ez lehetővé tenné számunkra, hogy először meglátogassuk a 8 (azaz 6, 4 és 3), majd az 5 (azaz null), majd a 2 (azaz 9) gyermek csomópontjait.
Végrehajtás
A BFS megvalósításához egy sor adatstruktúrát használnak. A sor tárolja a csomópontot, és „meglátogatottként” jelöli, amíg az összes szomszédos csúcsa meg nem jelenik.
A sor a First In First Out (FIFO) módszert követi. Ez azt jelenti, hogy a csomópont szomszédait a beszúrás sorrendjében keressük fel.
BFS varázslat:
- Adjon hozzá egy csomópontot a sorba
- Távolítsa el a csomópontot
- Szerezze be az eltávolított csomópont nem látogatott szomszédait, és adja hozzá őket a várólistához
- Ismételje meg az 1., 2. és 3. lépést, amíg a sor nem üres.
Most nézzünk meg néhány Leetcode problémát, és alkalmazzuk a tanultakat.
102. Bináris faszintű rend bejárása (nehézség: közepes)
A kérdés arra kér bennünket, hogy lépjünk át a grafikonon, és minden csomópontot kinyomtassunk egy csatolt listában. Ennek megoldásához mindössze annyit kell tennünk, hogy alkalmazzuk a varázsigét!
Ügyeljen arra, hogy jól megértse a kódot, mivel ez az az alapvető sablon, amelyet több probléma megoldására használunk. Tehát menjünk át rajta.
A fenti kódba először beillesztettük a gyökércsomópontot a sorba. Noha a sor nem üres, eltávolítottuk ezt a csomópontot a sorból, és beillesztettük a bal és jobb gyermekét a sorba.
De előtte ellenőriztük, hogy minden gyermeke semmis-e vagy sem. Ha null, akkor kaptunk volna egy Null Pointer kivételt.
A folyamat megismétlődik a sorban maradt következő elemekkel. A for hurokfenntartja, hogy minden csomópont listáját külön összekapcsolt listákban adja meg nekünk.
637. A bináris fa szintjeinek átlaga (nehézség: könnyű)
Ez a kérdés azt mondja, hogy meg kell találni a csomópontok átlagos értékét egy tömb bináris fa minden szintjén. Ez ugyanazt az eljárást követi, mint az előző problémánk egy kis csípéssel.
Mint láthatja, csak a sablonkód másolását és beillesztését tettük. Ezután egyszerűen teszünk egy összegváltozót a for ciklusba, amely megadhatja az egyes szintek csomópontértékeinek összegét. Ezt fogjuk használni a kívánt átlagunk kiszámításához.
429. N-ary fa szintű rendbejárás (nehézség: közepes)
Egy olyan fát, amelyben minden csomópontban legfeljebb N gyermek van, N-ágnak nevezzük.
Ez pontosan ugyanazt az eljárást követi, mint egy bináris fa bejárása, kivéve azt a tényt, hogy ide beillesztjük a csomópont összes gyermekét a sorba. Ne feledje, hogy a bináris fával kapcsolatos problémák megoldása közben csak az adott csomópont bal és jobb gyermekét illesztettük be a sorba.
Ez minden! Remélem, hogy ez segített jobban megérteni a BFS-t, és hogy élvezte az oktatóanyagot. Kérjük, ajánlja ezt a bejegyzést, ha úgy gondolja, hogy másnak is hasznos lehet!