TechCodeview

Prieš pažvelgdami į BFS ir DFS skirtumus, pirmiausia turėtume žinoti apie BFS ir DFS atskirai.

Kas yra BFS?

BFS reiškia Pirmoji paieška . Jis taip pat žinomas kaip lygio užsakymo perėjimas . Eilės duomenų struktūra naudojama „Breadth First Search“ peržiūrai. Kai grafike naudojame BFS algoritmą, bet kurį mazgą galime laikyti šakniniu mazgu.

Panagrinėkime toliau pateiktą pirmosios paieškos pločio schemą.

java parse string į int

Tarkime, kad mazgą 0 laikome šakniniu mazgu. Todėl judėjimas būtų pradėtas nuo 0 mazgo.

Kai mazgas 0 pašalinamas iš eilės, jis išspausdinamas ir pažymėtas kaip a aplankytas mazgas.

Kai 0 mazgas bus pašalintas iš eilės, gretimi 0 mazgo mazgai bus įterpti į eilę, kaip parodyta toliau:

Dabar mazgas 1 bus pašalintas iš eilės; jis atspausdinamas ir pažymimas kaip aplankytas mazgas

Kai 1 mazgas bus pašalintas iš eilės, visi gretimi 1 mazgo mazgai bus įtraukti į eilę. Gretimi 1 mazgo mazgai yra 0, 3, 2, 6 ir 5. Tačiau į eilę turime įterpti tik nelankytus mazgus. Kadangi 3, 2, 6 ir 5 mazgai yra nelankyti; todėl šie mazgai bus įtraukti į eilę, kaip parodyta toliau:

Kitas mazgas yra 3 eilėje. Taigi, 3 mazgas bus pašalintas iš eilės, jis bus atspausdintas ir pažymėtas kaip aplankytas, kaip parodyta žemiau:

Kai 3 mazgas bus pašalintas iš eilės, visi gretimi 3 mazgo mazgai, išskyrus aplankytus mazgus, bus įtraukti į eilę. Gretimi 3 mazgo mazgai yra 0, 1, 2 ir 4. Kadangi mazgai 0, 1 jau yra aplankyti, o 2 mazgas yra eilėje; todėl į eilę turime įterpti tik 4 mazgą.

np.unikali

Dabar kitas mazgas eilėje yra 2. Taigi 2 būtų ištrintas iš eilės. Jis atspausdinamas ir pažymėtas kaip aplankytas, kaip parodyta toliau:

Kai 2 mazgas bus pašalintas iš eilės, visi gretimi 2 mazgo mazgai, išskyrus aplankytus mazgus, bus įtraukti į eilę. Gretimi 2 mazgo mazgai yra 1, 3, 5, 6 ir 4. Kadangi 1 ir 3 mazgai jau buvo aplankyti, o 4, 5, 6 jau įtraukti į eilę; todėl mums nereikia įterpti jokio mazgo į eilę.

Kitas elementas yra 5. Taigi 5 būtų ištrintas iš eilės. Jis atspausdinamas ir pažymėtas kaip aplankytas, kaip parodyta toliau:

Kai 5 mazgas bus pašalintas iš eilės, visi gretimi 5 mazgo mazgai, išskyrus aplankytus mazgus, bus įtraukti į eilę. Gretimi 5 mazgo mazgai yra 1 ir 2. Kadangi abu mazgai jau buvo aplankyti; todėl nėra viršūnės, kurią būtų galima įterpti į eilę.

Kitas mazgas yra 6. Taigi, 6 būtų ištrintas iš eilės. Jis atspausdinamas ir pažymėtas kaip aplankytas, kaip parodyta toliau:

Kai 6 mazgas bus pašalintas iš eilės, visi gretimi 6 mazgo mazgai, išskyrus aplankytus mazgus, bus įtraukti į eilę. Gretimi 6 mazgo mazgai yra 1 ir 4. Kadangi 1 mazgas jau buvo aplankytas, o 4 mazgas jau įtrauktas į eilę; todėl nėra viršūnės, kurią būtų galima įterpti į eilę.

Kitas elementas eilėje yra 4. Taigi 4 būtų ištrintas iš eilės. Jis atspausdinamas ir pažymimas kaip aplankytas.

charakteris.palyginti java

Kai 4 mazgas bus pašalintas iš eilės, visi gretimi 4 mazgo mazgai, išskyrus aplankytus mazgus, bus įtraukti į eilę. 4 mazgo gretimi mazgai yra 3, 2 ir 6. Kadangi visi gretimi mazgai jau buvo aplankyti; taigi, į eilę įterpti viršūnės nėra.

Kas yra DFS?

DFS reiškia „Depth First Search“. DFS traversal yra naudojama kamino duomenų struktūra, kuri veikia LIFO (Last In First Out) principu. DFS sistemoje judėjimas gali būti pradėtas nuo bet kurio mazgo arba galime sakyti, kad bet kuris mazgas gali būti laikomas šakniniu mazgu, kol šakninis mazgas nepaminėtas užduotyje.

BFS atveju elementas, kuris ištrintas iš eilės, gretimi ištrinto mazgo mazgai pridedami prie eilės. Priešingai, naudojant DFS, elementas, kuris pašalinamas iš krūvos, tada į krūvą įtraukiamas tik vienas gretimas ištrinto mazgo mazgas.

Panagrinėkime toliau pateiktą pirmosios gilumos paieškos schemą.

Apsvarstykite 0 mazgą kaip šakninį mazgą.

Pirmiausia į krūvą įterpiame elementą 0, kaip parodyta žemiau:

Mazgas 0 turi du gretimus mazgus, t. y. 1 ir 3. Dabar perėjimui galime paimti tik vieną gretimą mazgą, 1 arba 3. Tarkime, kad svarstome mazgą 1; todėl 1 įterpiamas į krūvą ir atspausdinamas, kaip parodyta toliau:

Dabar pažvelgsime į gretimas 1 mazgo viršūnes. Nelankytos gretimos 1 mazgo viršūnės yra 3, 2, 5 ir 6. Galime svarstyti bet kurią iš šių keturių viršūnių. Tarkime, paimame 3 mazgą ir įdedame jį į krūvą, kaip parodyta žemiau:

Apsvarstykite neaplankytas gretimas 3 mazgo viršūnes. Nelankytos gretimos 3 mazgo viršūnės yra 2 ir 4. Galime paimti bet kurią iš viršūnių, ty 2 arba 4. Tarkime, paimame 2 viršūnę ir įterpiame ją į krūvą, kaip parodyta žemiau:

Nelankytos gretimos 2 mazgo viršūnės yra 5 ir 4. Galime pasirinkti bet kurią iš viršūnių, t. y. 5 arba 4. Tarkime, paimame viršūnę 4 ir įterpiame į krūvą, kaip parodyta žemiau:

Dabar apsvarstysime neaplankytas gretimas 4 mazgo viršūnes. Nelankyta gretima 4 mazgo viršūnė yra 6 mazgas. Todėl 6 elementas įterpiamas į krūvą, kaip parodyta žemiau:

kas yra Fredis Merkuris

Įdėję elementą 6 į krūvą, žiūrėsime į neaplankytas gretimas 6 mazgo viršūnes. Kadangi 6 mazgo neaplankytų gretimų viršūnių nėra, todėl negalime judėti toliau už 6 mazgo. Tokiu atveju atliksime atsitraukimas . Viršutinis elementas, ty 6, būtų išstumtas iš krūvos, kaip parodyta toliau:

mit pilna forma

Viršutinis krūvos elementas yra 4. Kadangi iš 4 mazgo neliko neaplankytų gretimų viršūnių; todėl 4 mazgas iškeliamas iš krūvos, kaip parodyta toliau:

Kitas aukščiausias elementas krūvoje yra 2. Dabar pažvelgsime į neaplankytas gretimas 2 mazgo viršūnes. Kadangi liko tik vienas neaplankytas mazgas, t. y. 5, tai 5 mazgas būtų įstumtas į krūvą virš 2 ir bus atspausdintas. kaip parodyta žemiau:

Dabar patikrinsime gretimas 5 mazgo viršūnes, kurios vis dar yra neaplankytos. Kadangi nebėra viršūnės, kurią būtų galima aplankyti, 5 elementą iškeliame iš krūvos, kaip parodyta žemiau:

Negalime judėti toliau 5, todėl turime atlikti grįžimą atgal. Grįžtant atgal, viršutinis elementas būtų iškeltas iš krūvos. Viršutinis elementas yra 5, kuris būtų išstumtas iš kamino, ir mes grįžtame į 2 mazgą, kaip parodyta toliau:

Dabar patikrinsime neaplankytas gretimas 2 mazgo viršūnes. Kadangi neliko gretimos viršūnės, kurią būtų galima aplankyti, todėl atliekame grįžimą atgal. Grįžtant atgal, viršutinis elementas, t. y. 2, būtų išstumtas iš krūvos, o mes grįžtame į 3 mazgą, kaip parodyta toliau:

Dabar patikrinsime neaplankytas gretimas 3 mazgo viršūnes. Kadangi gretimos viršūnės, kurią būtų galima aplankyti, nebėra, todėl atliekame grįžimą atgal. Grįžtant atgal, viršutinis elementas, t. y. 3, būtų iškeltas iš krūvos, ir mes grįžtame į 1 mazgą, kaip parodyta toliau:

Iššokę elementą 3, patikrinsime neaplankytas gretimas 1 mazgo viršūnes. Kadangi neliko aplankytos viršūnės; todėl bus atliktas grįžimas atgal. Grįžtant atgal, aukščiausias elementas, t. y. 1, būtų iškeltas iš krūvos, o mes grįžtame į mazgą 0, kaip parodyta toliau:

Patikrinsime gretimas 0 mazgo viršūnes, kurios vis dar yra neaplankytos. Kadangi neliko gretimos viršūnės, kurią būtų galima aplankyti, todėl atliekame atgalinį judėjimą. Šiuo atveju tik vienas elementas, t. y. 0, likęs krūvoje, būtų iškeltas iš krūvos, kaip parodyta toliau:

Kaip matome aukščiau esančiame paveikslėlyje, kaminas tuščias. Taigi, čia turime sustabdyti DFS perėjimą, o spausdinami elementai yra DFS perėjimo rezultatas.

Skirtumai tarp BFS ir DFS

Toliau pateikiami skirtumai tarp BFS ir DFS: