Kas yra BFS?
BFS yra algoritmas, naudojamas duomenims braižyti, medžiui ar einančioms struktūroms ieškoti. Algoritmas efektyviai aplanko ir tiksliai pažymi visus pagrindinius mazgus grafike.
Šis algoritmas grafike parenka vieną mazgą (pradinį arba šaltinio tašką) ir tada aplanko visus mazgus, esančius šalia pasirinkto mazgo. Kai algoritmas aplanko ir pažymi pradinį mazgą, jis juda link artimiausių nelankytų mazgų ir juos analizuoja.
Apsilankę visi mazgai yra pažymėti. Šios iteracijos tęsiasi tol, kol visi grafiko mazgai bus sėkmingai aplankyti ir pažymėti. Visa BFS forma yra „Pirmojo platumo“ paieška.
Šiame BSF vs. DFS dvejetainio medžio pamoka, sužinosite:
- Kas yra BFS?
- Kas yra DFS?
- BFS pavyzdys
- DFS pavyzdys
- Skirtumas tarp BFS ir DFS dvejetainio medžio
- BFS programos
- DFS programos
Kas yra DFS?
DFS yra grafikų ar medžių radimo ar perėjimo gylio kryptimi algoritmas. Algoritmo vykdymas prasideda šaknies mazge ir ištiria kiekvieną atšaką prieš grįžtant atgal. Jis naudoja kamino duomenų struktūrą, kad atsimintų, gautų kitą viršūnę ir pradėtų paiešką, kai bet kurioje iteracijoje pasirodo aklavietė. Visa DFS forma yra ieškojimas pirmiausia.
BFS pavyzdys
Šiame DFS pavyzdyje mes panaudojome grafiką, turintį 6 viršūnes.
BFS pavyzdys
1 žingsnis)
Turite septynių skaičių grafiką, svyruojantį nuo 0 iki 6.
2 žingsnis)
0 arba nulis pažymėtas kaip šakninis mazgas.
3 žingsnis)
0 aplankoma, pažymima ir įtraukiama į eilės duomenų struktūrą.
4 žingsnis)
Likę 0 gretimų ir neaplankytų mazgų aplankomi, pažymimi ir įterpiami į eilę.
5 žingsnis)
Kertamos iteracijos kartojamos, kol aplankomi visi mazgai.
DFS pavyzdys
Šiame DFS pavyzdyje mes panaudojome nenukreiptą grafiką, turintį 5 viršūnes.
1 žingsnis)
Pradėjome nuo viršūnės 0. Algoritmas pradedamas įtraukiant jį į aplankytą sąrašą ir tuo pačiu įdedant visas gretimas viršūnes į duomenų struktūrą, vadinamą „stack“.
2 žingsnis)
Apsilankysite elemente, kuris yra kamino viršuje, pavyzdžiui, 1 ir eisite į gretimus jo mazgus. Taip yra todėl, kad 0 jau aplankyta. Todėl mes aplankome 2 viršūnę.
3 žingsnis)
2 viršūnėje yra nelankyta netoliese esanti viršūnė 4-oje. Todėl mes įtraukiame tai į rietuvę ir aplankome ją.
4 žingsnis)
Galiausiai aplankysime paskutinę 3 viršūnę, joje nėra jokių neaplankytų gretimų mazgų. Mes baigėme grafiko perėjimą naudodami DFS algoritmą.
Skirtumas tarp BFS ir DFS dvejetainio medžio
| BFS | DFS |
| BFS randa trumpiausią kelią iki tikslo. | DFS eina į potemio apačią, tada grįžta atgal. |
| Visa BFS forma yra „Breadth-First Search“. | Visa DFS forma yra „Depth First Search“. |
| Ji naudoja eilę, kad galėtų sekti kitą aplankytą vietą. | Jis naudoja kaminą, kad galėtų sekti kitą aplankytą vietą. |
| BFS eina pagal medžio lygį. | DFS važiuoja pagal medžio gylį. |
| Jis įgyvendinamas naudojant FIFO sąrašą. | Jis įgyvendinamas naudojant LIFO sąrašą. |
| Tam reikia daugiau atminties, palyginti su DFS. | Tam reikia mažiau atminties, palyginti su BFS. |
| Šis algoritmas pateikia sekliausio kelio sprendimą. | Šis algoritmas negarantuoja sekliausio kelio sprendimo. |
| BFS nereikia grįžti atgal. | DFS reikia grįžti atgal. |
| Niekada negali būti įstrigęs baigtinėse kilpose. | Galite būti įstrigę begalinėse kilpose. |
| Jei nerandate jokio tikslo, gali reikėti išplėsti daugelį mazgų, kol bus rastas sprendimas. | Jei nerandate jokio tikslo, gali atsirasti lapų mazgas. |
BFS programos
Čia yra BFS programos:
Nesverti grafikai:
BFS algoritmas gali lengvai sukurti trumpiausią kelią ir minimalų tarpatramį medį, kad būtų galima aplankyti visas grafiko viršūnes per trumpiausią įmanomą laiką labai tiksliai.
P2P tinklai:
BFS gali būti įdiegtas norint rasti visus artimiausius ar kaimyninius mazgus tinkle „peer to peer“. Tai padės reikalingus duomenis rasti greičiau.
Žiniatinklio tikrintuvai:
Paieškos sistemos ar žiniatinklio tikrintuvai gali lengvai sukurti kelis indeksų lygius naudodami BFS. BFS diegimas prasideda nuo šaltinio, kuris yra tinklalapis, ir tada jis aplanko visas to šaltinio nuorodas.
Tinklo transliavimas:
Transliuojamas paketas vadovaujamasi BFS algoritmu, kad surastų ir pasiektų visus mazgus, kuriems jis turi adresą.
DFS programos
Čia yra svarbios DFS programos:
Svertinis grafikas:
Svertiniame grafike DFS grafiko perėjimas sukuria trumpiausią kelio medį ir mažiausiai apimantį medį.
Ciklo nustatymas diagramoje:
Grafikas turi ciklą, jei DFS metu radome galinį kraštą. Todėl grafike turėtume paleisti DFS ir patikrinti, ar nėra užpakalinių kraštų.
Kelio radimas:
Mes galime specializuotis DFS algoritme, kad ieškotume kelio tarp dviejų viršūnių.
Topologinis rūšiavimas:
Jis visų pirma naudojamas planuoti užduotis iš nurodytų darbo grupių priklausomybių. Informatikoje jis naudojamas planuojant instrukcijas, duomenų eiliškumą, logikos sintezę, nustatant kompiliavimo užduočių tvarką.
Ieškoma tvirtai sujungtų grafiko komponentų:
Jis naudojamas DFS grafike, kai yra kelias nuo kiekvieno grafiko viršūnės iki kitų likusių viršūnių.
Galvosūkių sprendimas tik su vienu sprendimu:
DFS algoritmą galima lengvai pritaikyti ieškant visų labirinto sprendimų, įtraukiant mazgus esamame kelyje į aplankytą rinkinį.
PAGRINDINIAI SKIRTUMAI:
- BFS randa trumpiausią kelią iki tikslo, o DFS eina į potemio apačią, tada grįžta atgal.
- Visa BFS forma yra „Pirmojo pločio paieška“, o visa „DFS“ - „Pirmoji gylio paieška“.
- BFS naudoja eilę sekti kitą aplankytą vietą. kadangi DFS naudoja kaminą, kad galėtų sekti kitą aplankytą vietą.
- BFS važiuoja pagal medžio lygį, o DFS - pagal medžio gylį.
- BFS įgyvendinamas naudojant FIFO sąrašą, kita vertus, DFS įgyvendinamas naudojant LIFO sąrašą.
- BFS jūs niekada negalite būti įkalinti į baigtines kilpas, o DFS - į begalines kilpas.