Preden pogledamo razlike med BFS in DFS, moramo najprej vedeti o BFS in DFS ločeno.

Kaj je BFS?

BFS pomeni Najprej iskanje v širino . Znan je tudi kot prečkanje reda ravni . Podatkovna struktura Queue se uporablja za prečkanje Breadth First Search. Ko uporabljamo algoritem BFS za prečkanje v grafu, lahko vsako vozlišče obravnavamo kot korensko vozlišče.

Oglejmo si spodnji graf za prvo iskanje po širini.

binarni drevesni tipi

Recimo, da obravnavamo vozlišče 0 kot korensko vozlišče. Zato bi se prečkanje začelo od vozlišča 0.

Ko je vozlišče 0 odstranjeno iz čakalne vrste, se natisne in označi kot a obiskano vozlišče.

Ko je vozlišče 0 odstranjeno iz čakalne vrste, bodo sosednja vozlišča vozlišča 0 vstavljena v čakalno vrsto, kot je prikazano spodaj:

Zdaj bo vozlišče 1 odstranjeno iz čakalne vrste; se natisne in označi kot obiskano vozlišče

Ko je vozlišče 1 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 1 dodana v čakalno vrsto. Sosednja vozlišča vozlišča 1 so 0, 3, 2, 6 in 5. Toda v čakalno vrsto moramo vstaviti samo neobiskana vozlišča. Ker so vozlišča 3, 2, 6 in 5 neobiskana; zato bodo ta vozlišča dodana v čakalno vrsto, kot je prikazano spodaj:

Naslednje vozlišče je 3 v čakalni vrsti. Vozlišče 3 bo torej odstranjeno iz čakalne vrste, natisnjeno in označeno kot obiskano, kot je prikazano spodaj:

Ko je vozlišče 3 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 3, razen obiskanih vozlišč, dodana v čakalno vrsto. Sosednja vozlišča vozlišča 3 so 0, 1, 2 in 4. Ker so vozlišča 0, 1 že obiskana, vozlišče 2 pa je prisotno v čakalni vrsti; zato moramo v čakalno vrsto vstaviti samo vozlišče 4.

instanciranje jave

Zdaj je naslednje vozlišče v čakalni vrsti 2. Torej bi bilo 2 izbrisano iz čakalne vrste. Natisne se in označi kot obiskano, kot je prikazano spodaj:

Ko je vozlišče 2 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 2, razen obiskanih vozlišč, dodana v čakalno vrsto. Sosednja vozlišča vozlišča 2 so 1, 3, 5, 6 in 4. Ker sta bili vozlišči 1 in 3 že obiskani, 4, 5, 6 pa so že dodana v čakalno vrsto; zato nam v čakalno vrsto ni treba vstaviti nobenega vozlišča.

Naslednji element je 5. Torej bi bil 5 izbrisan iz čakalne vrste. Natisne se in označi kot obiskano, kot je prikazano spodaj:

Ko je vozlišče 5 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 5, razen obiskanih vozlišč, dodana v čakalno vrsto. Sosednji vozlišči vozlišča 5 sta 1 in 2. Ker sta bili obe vozlišči že obiskani; zato ni vozlišča, ki bi ga bilo treba vstaviti v čakalno vrsto.

Naslednje vozlišče je 6. Torej bi bilo 6 izbrisano iz čakalne vrste. Natisne se in označi kot obiskano, kot je prikazano spodaj:

Ko je vozlišče 6 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 6, razen obiskanih vozlišč, dodana v čakalno vrsto. Sosednji vozlišči vozlišča 6 sta 1 in 4. Ker je bilo vozlišče 1 že obiskano in je vozlišče 4 že dodano v čakalno vrsto; zato ni vozlišča, ki bi ga bilo treba vstaviti v čakalno vrsto.

Naslednji element v čakalni vrsti je 4. Torej bi bil 4 izbrisan iz čakalne vrste. Natisne se in označi kot obiskano.

Ko je vozlišče 4 odstranjeno iz čakalne vrste, bodo vsa sosednja vozlišča vozlišča 4, razen obiskanih vozlišč, dodana v čakalno vrsto. Sosednja vozlišča vozlišča 4 so 3, 2 in 6. Ker so bila vsa sosednja vozlišča že obiskana; torej ni vozlišča, ki bi ga bilo treba vstaviti v čakalno vrsto.

preberite datoteko csv v javi

Kaj je DFS?

DFS pomeni Depth First Search. Pri prehodu DFS se uporablja podatkovna struktura sklada, ki deluje po principu LIFO (Last In First Out). V DFS se lahko prečkanje začne iz katerega koli vozlišča ali pa lahko rečemo, da se lahko katero koli vozlišče obravnava kot korensko vozlišče, dokler korensko vozlišče ni omenjeno v problemu.

V primeru BFS, elementa, ki je izbrisan iz čakalne vrste, se sosednja vozlišča izbrisanega vozlišča dodajo v čakalno vrsto. V nasprotju s tem se v DFS elementu, ki je odstranjen iz sklada, nato v sklad doda samo eno sosednje vozlišče izbrisanega vozlišča.

Oglejmo si spodnji graf za prečkanje iskanja najprej v globino.

Vozlišče 0 upoštevajte kot korensko vozlišče.

Najprej vstavimo element 0 v sklad, kot je prikazano spodaj:

koliko tednov na mesec

Vozlišče 0 ima dve sosednji vozlišči, tj. 1 in 3. Zdaj lahko za prečkanje vzamemo samo eno sosednje vozlišče, bodisi 1 bodisi 3. Recimo, da obravnavamo vozlišče 1; zato je 1 vstavljen v sklad in se natisne, kot je prikazano spodaj:

Zdaj si bomo ogledali sosednja oglišča vozlišča 1. Neobiskana sosednja oglišča vozlišča 1 so 3, 2, 5 in 6. Upoštevamo lahko katero koli od teh štirih oglišč. Recimo, da vzamemo vozlišče 3 in ga vstavimo v sklad, kot je prikazano spodaj:

Upoštevajte neobiskana sosednja oglišča vozlišča 3. Neobiskana sosednja oglišča vozlišča 3 sta 2 in 4. Vzamemo lahko eno od oglišč, tj. 2 ali 4. Recimo, da vzamemo oglišče 2 in ga vstavimo v sklad, kot je prikazano spodaj:

Neobiskani sosednji točki vozlišča 2 sta 5 in 4. Izberemo lahko eno od tock, tj. 5 ali 4. Recimo, da vzamemo točko 4 in jo vstavimo v sklad, kot je prikazano spodaj:

Zdaj bomo obravnavali neobiskana sosednja oglišča vozlišča 4. Neobiskano sosednje oglišče vozlišča 4 je vozlišče 6. Zato je element 6 vstavljen v sklad, kot je prikazano spodaj:

Po vstavitvi elementa 6 v sklad si bomo ogledali neobiskana sosednja oglišča vozlišča 6. Ker ni neobiskanih sosednjih oglišč vozlišča 6, se ne moremo premakniti onkraj vozlišča 6. V tem primeru bomo izvedli sledenje nazaj . Najvišji element, tj. 6, bi izskočil iz sklada, kot je prikazano spodaj:

Najvišji element v skladu je 4. Ker od vozlišča 4 ni neobiskanih sosednjih tock; zato je vozlišče 4 izstopilo iz sklada, kot je prikazano spodaj:

razdeljen z nizom java

Naslednji najvišji element v skladu je 2. Zdaj si bomo ogledali neobiskana sosednja oglišča vozlišča 2. Ker je ostalo samo eno neobiskano vozlišče, tj. 5, bi bilo vozlišče 5 potisnjeno v sklad nad 2 in se natisne kot je prikazano spodaj:

Zdaj bomo preverili sosednja oglišča vozlišča 5, ki še niso obiskana. Ker ni več nobene točke, ki bi jo bilo treba obiskati, izločimo element 5 iz sklada, kot je prikazano spodaj:

Ne moremo se premakniti več za 5, zato moramo izvesti povratno sledenje. Pri povratnem sledenju bi najvišji element izskočil iz sklada. Najvišji element je 5, ki bi izskočil iz sklada, in premaknemo se nazaj na vozlišče 2, kot je prikazano spodaj:

Sedaj bomo preverili neobiskana sosednja oglišča vozlišča 2. Ker ni več sosednjega oglišča, ki bi ga lahko obiskali, izvajamo sledenje nazaj. Pri sledenju nazaj bi najvišji element, tj. 2, izstopil iz sklada, mi pa se premaknemo nazaj na vozlišče 3, kot je prikazano spodaj:

Sedaj bomo preverili neobiskana sosednja oglišča vozlišča 3. Ker ni več sosednjih oglišč, ki bi jih lahko obiskali, izvajamo sledenje nazaj. Pri sledenju nazaj bi najvišji element, tj. 3, izstopil iz sklada in premaknemo se nazaj na vozlišče 1, kot je prikazano spodaj:

Po izstopu elementa 3 bomo preverili neobiskana sosednja oglišča vozlišča 1. Ker ni več oglišča, ki bi ga lahko obiskali; zato bo izvedeno sledenje nazaj. Pri sledenju nazaj bi bil najvišji element, tj. 1, izstopil iz sklada, mi pa se premaknemo nazaj na vozlišče 0, kot je prikazano spodaj:

Preverili bomo sosednja oglišča vozlišča 0, ki še niso obiskana. Ker ni nobenega sosednjega vozlišča, ki bi ga bilo treba obiskati, izvajamo sledenje nazaj. Pri tem bi samo en element, tj. 0, ki ostane v skladu, izstopil iz sklada, kot je prikazano spodaj:

Kot lahko opazimo na zgornji sliki, je sklad prazen. Torej, tukaj moramo ustaviti prehod DFS, elementi, ki se natisnejo, pa so rezultat prehoda DFS.

Razlike med BFS in DFS

Med BFS in DFS so naslednje razlike: