Kas ir BFS?
BFS ir algoritms, ko izmanto, lai attēlotu datus, meklētu koku vai šķērsotu struktūras. Algoritms efektīvi apskata un iezīmē grafikā visus galvenos mezglus precīzā platumā.
Šis algoritms diagrammā izvēlas vienu mezglu (sākuma vai avota punktu) un pēc tam apmeklē visus mezglus, kas atrodas blakus atlasītajam mezglam. Kad algoritms apmeklē un atzīmē sākuma mezglu, tas virzās uz tuvākajiem neapmeklētajiem mezgliem un tos analizē.
Pēc apmeklējuma visi mezgli tiek atzīmēti. Šīs iterācijas turpinās, līdz visi diagrammas mezgli ir veiksmīgi apmeklēti un atzīmēti. Pilna BFS forma ir pirmais platums.
Šajā BSF Vs. DFS binārā koka apmācība, jūs uzzināsiet:
- Kas ir BFS?
- Kas ir DFS?
- BFS piemērs
- DFS piemērs
- Atšķirība starp BFS un DFS bināro koku
- BFS pielietojumi
- DFS lietojumi
Kas ir DFS?
DFS ir algoritms grafiku vai koku atrašanai vai šķērsošanai dziļuma virzienā. Algoritma izpilde sākas saknes mezglā un pirms atzarošanas pēta katru atzaru. Tas izmanto kaudzes datu struktūru, lai atcerētos, iegūtu nākamo virsotni un sāktu meklēšanu ikreiz, kad kādā atkārtojumā parādās strupceļš. Pilna DFS forma ir meklēšana dziļumā.
BFS piemērs
Šajā DFS piemērā mēs izmantojām diagrammu ar 6 virsotnēm.
BFS piemērs
1. darbība)
Jums ir septiņu skaitļu diagramma, kas svārstās no 0 līdz 6.
2. solis)
0 vai nulle ir atzīmēta kā saknes mezgls.
3. solis)
0 tiek apmeklēts, atzīmēts un ievietots rindas datu struktūrā.
4. solis)
Atlikušie 0 blakus esošie un neapmeklētie mezgli tiek apmeklēti, atzīmēti un ievietoti rindā.
5. solis)
Ceļojošās iterācijas tiek atkārtotas, līdz tiek apmeklēti visi mezgli.
DFS piemērs
Šajā DFS piemērā mēs izmantojām nenovirzītu grafiku ar 5 virsotnēm.
1. darbība)
Mēs esam sākuši no 0. virsotnes. Algoritms sākas, ievietojot to apmeklētajā sarakstā un vienlaikus ievietojot visas blakus esošās virsotnes datu struktūrā, ko sauc par kaudzi.
2. solis)
Jūs apmeklēsiet elementu, kas atrodas kaudzes augšdaļā, piemēram, 1, un dodieties uz blakus esošajiem mezgliem. Tas ir tāpēc, ka 0 jau ir apmeklēts. Tāpēc mēs apmeklējam 2. virsotni.
3. solis)
2. virsotnei ir neapmeklēta tuvumā esošā virsotne 4. Tāpēc mēs to pievienojam kaudzē un apmeklējam to.
4. solis)
Visbeidzot, mēs apmeklēsim pēdējo 3. virsotni, tajā nav neviena neapmeklēta blakus esošā mezgla. Mēs esam pabeiguši diagrammas šķērsošanu, izmantojot DFS algoritmu.
Atšķirība starp BFS un DFS bināro koku
| BFS | DFS |
| BFS atrod īsāko ceļu līdz galamērķim. | DFS iet apakšgrupas apakšā, pēc tam atgriežas. |
| Pilna BFS forma ir Breadth-First Search. | Pilna DFS forma ir dziļuma pirmā meklēšana. |
| Tā izmanto rindu, lai sekotu nākamajai apmeklējamai vietai. | Tas izmanto kaudzi, lai sekotu nākamajai apmeklējamai vietai. |
| BFS šķērso atbilstoši koka līmenim. | DFS šķērso koku dziļumu. |
| To īsteno, izmantojot FIFO sarakstu. | To īsteno, izmantojot LIFO sarakstu. |
| Tas prasa vairāk atmiņas, salīdzinot ar DFS. | Tas prasa mazāk atmiņas, salīdzinot ar BFS. |
| Šis algoritms nodrošina seklākā ceļa risinājumu. | Šis algoritms negarantē seklākā ceļa risinājumu. |
| BFS nav nepieciešams atgriezties. | DFS ir jāatkāpjas. |
| Jūs nekad nevarat būt ieslodzīts ierobežotās cilpās. | Jūs varat būt ieslodzīts bezgalīgās cilpās. |
| Ja neatrodat mērķi, pirms risinājuma atrašanas, iespējams, būs jāpaplašina daudzi mezgli. | Ja neatrodat nevienu mērķi, var notikt lapu mezglu atkāpšanās. |
BFS pielietojumi
Šeit ir BFS lietojumprogrammas:
Nesvērti grafiki:
BFS algoritms var viegli izveidot īsāko ceļu un minimālo aptverošo koku, lai pēc iespējas īsākā laikā ar lielu precizitāti apmeklētu visas diagrammas virsotnes.
P2P tīkli:
BFS var ieviest, lai atrastu visus tuvākos vai blakus esošos mezglus vienādranga tīklā. Tas ātrāk atradīs nepieciešamos datus.
Tīmekļa rāpuļprogrammas:
Meklētājprogrammas vai tīmekļa rāpuļprogrammas var viegli izveidot vairākus indeksu līmeņus, izmantojot BFS. BFS ieviešana sākas no avota, kas ir tīmekļa lapa, un pēc tam tā apmeklē visas saites no šī avota.
Tīkla apraide:
Pārraidīto paketi vada BFS algoritms, lai atrastu un sasniegtu visus mezglus, kuriem tai ir adrese.
DFS lietojumi
Šeit ir svarīgas DFS lietojumprogrammas:
Svērtais grafiks:
Svērtajā grafikā DFS diagrammas šķērsošana ģenerē īsāko ceļa koku un minimālo aptverošo koku.
Cikla noteikšana diagrammā:
Grafikam ir cikls, ja DFS laikā mēs atradām aizmugurējo malu. Tāpēc mums vajadzētu palaist DFS grafikam un pārbaudīt aizmugures malas.
Ceļa Meklēšana:
Mēs varam specializēties DFS algoritmā, lai meklētu ceļu starp divām virsotnēm.
Topoloģiskā šķirošana:
To galvenokārt izmanto, lai ieplānotu darbus no norādītajām atkarībām starp darba grupām. Datorzinātnēs to izmanto instrukciju plānošanā, datu serializācijā, loģikas sintēzē, kompilācijas uzdevumu secības noteikšanā.
Meklējot stipri savienotus grafika komponentus:
Tas tika izmantots DFS diagrammā, ja no katra grafika virsotnes ir ceļš uz citiem atlikušajiem virsotnēm.
Mīklu risināšana tikai ar vienu risinājumu:
DFS algoritmu var viegli pielāgot, lai meklētu visus labirinta risinājumus, apmeklētajā komplektā iekļaujot mezglus esošajā ceļā.
GALVENĀS ATŠĶIRĪBAS:
- BFS atrod īsāko ceļu līdz galamērķim, turpretim DFS iet uz apakškoku apakšdaļu, pēc tam atgriežas.
- Pilna BFS forma ir Breadth-First Search, savukārt pilnā DFS forma ir First Depth Search.
- BFS izmanto rindu, lai sekotu nākamajai apmeklējamai vietai. tā kā DFS izmanto kaudzi, lai sekotu nākamajai apmeklējamai vietai.
- BFS šķērso atbilstoši koka līmenim, bet DFS - atbilstoši koka dziļumam.
- BFS tiek ieviests, izmantojot FIFO sarakstu, no otras puses, DFS tiek ieviests, izmantojot LIFO sarakstu.
- BFS jūs nekad nevarat būt ieslodzīts ierobežotās cilpās, turpretī DFS jūs varat ieslodzīt bezgalīgās cilpās.