Kas ir BFS algoritms (pirmā platuma meklēšana)?
Breadth-first search (BFS) ir algoritms, ko izmanto, lai attēlotu datus vai meklētu koku vai šķērsojošas struktūras. Pilna BFS forma ir pirmais platums.
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. Atcerieties, ka BFS šiem mezgliem piekļūst pa vienam.
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.
Šajā algoritma apmācībā jūs uzzināsiet:
- Kas ir BFS algoritms (pirmā platuma meklēšana)?
- Kas ir diagrammas šķērsošana?
- BFS algoritma arhitektūra
- Kāpēc mums vajadzīgs BFS algoritms?
- Kā darbojas BFS algoritms?
- BFS algoritma piemērs
- BFS algoritma noteikumi
- BFS algoritma pielietojums
Kas ir diagrammas šķērsošana?
Grafa šķērsošana ir bieži izmantota metodika virsotnes atrašanās vietas noteikšanai diagrammā. Tas ir uzlabots meklēšanas algoritms, kas var ātri un precīzi analizēt diagrammu, kā arī atzīmēt apmeklēto virsotņu secību. Šis process ļauj ātri apmeklēt katru diagrammas mezglu, neieslēdzot to bezgalīgajā lokā.
BFS algoritma arhitektūra
- Dažādos datu līmeņos jūs varat atzīmēt jebkuru mezglu kā sākuma vai sākuma mezglu, lai sāktu šķērsošanu. BFS apmeklēs mezglu, atzīmēs to kā apmeklētu un ievietos rindā.
- Tagad BFS apmeklēs tuvākos un neapmeklētos mezglus un tos atzīmēs. Šīs vērtības tiek pievienotas arī rindai. Rinda darbojas pēc FIFO modeļa.
- Līdzīgā veidā tiek analizēti atlikušie tuvākie un neapmeklētie diagrammas mezgli, kas atzīmēti un pievienoti rindai. Šie vienumi tiek izdzēsti no rindas kā saņemšanas un tiek izdrukāti kā rezultāts.
Kāpēc mums vajadzīgs BFS algoritms?
Ir vairāki iemesli, kāpēc BFS algoritmu izmantot kā datu kopas meklēšanu. Daži no vissvarīgākajiem aspektiem, kas padara šo algoritmu par pirmo izvēli, ir:
- BFS ir noderīgs, lai analizētu mezglus diagrammā un izveidotu īsāko pārvietošanās ceļu pa tiem.
- BFS var šķērsot grafiku ar mazāko atkārtojumu skaitu.
- BFS algoritma arhitektūra ir vienkārša un izturīga.
- BFS algoritma rezultātam ir augsts precizitātes līmenis salīdzinājumā ar citiem algoritmiem.
- BFS atkārtojumi ir viengabalaini, un nav iespējas, ka šis algoritms nokļūst bezgalīgas cilpas problēmā.
Kā darbojas BFS algoritms?
Grafika šķērsošanai nepieciešams, lai algoritms apmeklētu, pārbaudītu un / vai atjauninātu katru atsevišķo neapmeklēto mezglu kokveida struktūrā. Grafu šķērsošana tiek kategorizēta pēc secības, kādā tie apmeklē diagrammas mezglus.
BFS algoritms sāk darbību no grafika pirmā vai sākuma mezgla un pamatīgi to šķērso. Kad tas veiksmīgi šķērso sākotnējo mezglu, tiek apmeklēta un atzīmēta nākamā negrozītā virsotne grafikā.
Tādējādi jūs varat teikt, ka visi mezgli, kas atrodas blakus pašreizējai virsotnei, tiek apmeklēti un šķērsoti pirmajā atkārtojumā. Lai ieviestu BFS algoritmu, tiek izmantota vienkārša rindu metodika, un tā sastāv no šādām darbībām:
1. darbība)
Katra diagrammas virsotne vai mezgls ir zināms. Piemēram, jūs varat atzīmēt mezglu kā V.
2. solis)
Gadījumā, ja virsotnei V nav piekļuves, pievienojiet virsotni V BFS rindā
3. solis)
Sāciet BFS meklēšanu un pēc pabeigšanas atzīmējiet virsotni V kā apmeklētu.
4. solis)
BFS rinda joprojām nav tukša, tāpēc no rindas noņemiet diagrammas virsotni V.
5. solis)
Iegūstiet visas atlikušās diagrammas virsotnes, kas atrodas blakus virsotnei V
6. solis)
Pieņemsim, ka katrai blakus esošajai virsotnei V1, ja tā vēl nav apmeklēta, pievienojiet V1 BFS rindai
7. solis)
BFS apmeklēs V1, atzīmēs to kā apmeklētu un izdzēsīs to no rindas.
BFS algoritma 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.
BFS algoritma noteikumi
Šeit ir svarīgi noteikumi BFS algoritma izmantošanai:
- BFS izmanto rindas (FIFO-First in First Out) datu struktūru.
- Jūs atzīmējat jebkuru diagrammas mezglu kā sakni un sākat šķērsot datus no tā.
- BFS šķērso visus diagrammas mezglus un turpina tos nomest kā pabeigtus.
- BFS apmeklē blakus esošo neapmeklēto mezglu, atzīmē to kā pabeigtu un ievieto rindā.
- Noņem iepriekšējo virsotni no rindas, ja blakus esošā virsotne netiek atrasta.
- BFS algoritms atkārtojas, līdz visas diagrammas virsotnes ir veiksmīgi šķērsotas un atzīmētas kā pabeigtas.
- Datu šķērsošanas laikā no jebkura mezgla BFS neizraisa cilpas.
BFS algoritma pielietojums
Apskatīsim dažas reālās dzīves lietojumprogrammas, kurās BFS algoritma ieviešana var būt ļoti efektīva.
- 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.
- Navigācijas sistēmas: BFS var palīdzēt atrast visas blakus esošās vietas no galvenās vai avota vietas.
- Tīkla apraide: Apraides paketi vada BFS algoritms, lai atrastu un sasniegtu visus mezglus, kuriem tai ir adrese.
Kopsavilkums
- Diagrammas šķērsošana ir unikāls process, kas prasa algoritmam apmeklēt, pārbaudīt un / vai atjaunināt katru atsevišķo neapmeklēto mezglu kokveidīgajā struktūrā. BFS algoritms darbojas pēc līdzīga principa.
- Algoritms ir noderīgs, lai analizētu mezglus diagrammā un izveidotu īsāko pārvietošanās ceļu caur tiem.
- Algoritms šķērso grafiku pēc iespējas mazākā atkārtojumu skaitā un pēc iespējas īsākā laikā.
- BFS diagrammā izvēlas vienu mezglu (sākotnējo vai avota punktu) un pēc tam apmeklē visus mezglus, kas atrodas blakus atlasītajam mezglam. BFS šiem mezgliem piekļūst pa vienam.
- Apmeklētos un atzīmētos datus BFS ievieto rindā. Rinda darbojas pēc principa “pirmais iekšā pirmais”. Tādējādi vispirms diagrammā ievietotais elements vispirms tiek izdzēsts un tiek izdrukāts.
- BFS algoritms nekad nevar iekļūt bezgalīgā lokā.
- Augstas precizitātes un stabilas ieviešanas dēļ BFS tiek izmantots vairākos reālās dzīves risinājumos, piemēram, P2P tīklos, tīmekļa rāpuļprogrammās un tīkla apraidē.