Mis on BFS?
BFS on algoritm, mida kasutatakse andmete joonistamiseks või puu otsimiseks või läbivate struktuuride otsimiseks. Algoritm külastab ja tähistab graafikus kõiki võtmesõlme tõhusalt ja täpselt.
See algoritm valib graafikust ühe sõlme (alg- või lähtekoha) ja külastab seejärel kõiki valitud sõlmega külgnevaid sõlme. Kui algoritm külastab ja tähistab algussõlme, liigub see lähimate külastamata sõlmede suunas ja analüüsib neid.
Pärast külastamist märgitakse kõik sõlmed. Need iteratsioonid jätkuvad seni, kuni graafiku kõik sõlmed on edukalt külastatud ja märgistatud. BFS-i täielik vorm on laius-esimene otsing.
Selles BSF vs. DFS-i binaarpuu õpetus, saate teada:
- Mis on BFS?
- Mis on DFS?
- BFS-i näide
- DFS-i näide
- Erinevus BFS ja DFS binaarpuu vahel
- BFS-i rakendused
- DFS-i rakendused
Mis on DFS?
DFS on algoritm graafikute või puude leidmiseks või läbimiseks sügavuse suunas. Algoritmi käivitamine algab juursõlmest ja uurib iga haru enne tagasiteed. See kasutab virna andmestruktuuri mäletamiseks, järgneva tipu saamiseks ja otsingu alustamiseks alati, kui mis tahes iteratsioonis ilmub tupik. DFS-i täielik vorm on sügavus-esimene otsing.
BFS-i näide
Järgmises DFS-i näites oleme kasutanud graafi, millel on 6 tippu.
BFS-i näide
Samm 1)
Teil on seitsmest numbrist koosnev graafik vahemikus 0–6.
2. samm)
0 või null on märgitud juursõlmeks.
3. samm)
0 külastatakse, märgitakse ja lisatakse järjekorra andmestruktuuri.
4. samm)
Ülejäänud 0 külgnevat ja külastamata sõlme külastatakse, märgitakse ja sisestatakse järjekorda.
5. samm)
Läbivaid kordusi korratakse seni, kuni kõik sõlmed on külastatud.
DFS-i näide
Järgmises DFS-i näites oleme kasutanud suunamata graafi, millel on 5 tippu.
Samm 1)
Alustasime tipust 0. Algoritm algab selle lisamisest külastatud loendisse ja kõigi selle kõrvuti asetsevate tippude üheaegse lisamisega andmestruktuuri, mida nimetatakse virnaks.
2. samm)
Külastate elementi, mis on virna ülaosas, näiteks 1 ja minge selle külgnevatesse sõlmedesse. Sellepärast, et 0 on juba külastatud. Seetõttu külastame tippu 2.
3. samm)
Tipul 2 on külastamata lähedal asuv tipp tipus 4. Seetõttu lisame selle virnasse ja külastame seda.
4. samm)
Lõpuks külastame viimast tippu 3, sellel pole ühtegi külastamata külgnevat sõlme. Oleme graafiku läbimise DFS-algoritmi abil lõpetanud.
Erinevus BFS ja DFS binaarpuu vahel
| BFS | DFS |
| BFS leiab sihtkohta lühima tee. | DFS läheb alampuu põhja, seejärel pöördub tagasi. |
| BFS-i täielik vorm on otsingu laius. | DFS-i täielik vorm on sügavus esimene otsing. |
| Järgmise külastatava asukoha jälgimiseks kasutatakse järjekorda. | Järgmise külastatava asukoha jälgimiseks kasutab see virna. |
| BFS läbib vastavalt puu tasemele. | DFS läbib vastavalt puu sügavusele. |
| Seda rakendatakse FIFO loendi abil. | Seda rakendatakse LIFO loendi abil. |
| See nõuab DFS-iga võrreldes rohkem mälu. | See nõuab BFS-iga võrreldes vähem mälu. |
| See algoritm annab madalaima raja lahenduse. | See algoritm ei taga kõige madalama raja lahendust. |
| BFS-is pole vaja tagasiteed. | DFS-is on vaja tagasi pöörduda. |
| Te ei saa kunagi olla piiratud silmuste lõksus. | Võite jääda lõpututesse silmustesse. |
| Kui te ei leia ühtegi eesmärki, peate võib-olla enne lahenduse leidmist paljusid sõlme laiendama. | Kui te ei leia eesmärki, võib tekkida lehesõlme tagasitee. |
BFS-i rakendused
Siin on BFS-i rakendused:
Kaalumata graafikud:
BFS-i algoritm võib hõlpsasti luua lühima tee ja minimaalse läbiva puu, et külastada graafiku kõiki tippe võimalikult lühikese aja jooksul suure täpsusega.
P2P võrgud:
BFS-i saab rakendada kõigi lähimate või naabruses asuvate sõlmede leidmiseks võrdõigusvõrgus. See leiab vajalikud andmed kiiremini.
Veebirobotid:
Otsingumootorid või veebirobotid saavad BFS-i abil hõlpsasti luua mitu indeksitaset. BFS-i juurutamine algab allikast, milleks on veebileht, ja seejärel külastab see kõik selle allika lingid.
Võrgu ringhääling:
Levitatav pakett juhindub BFS-i algoritmist kõigi sõlmede leidmiseks ja nendeni jõudmiseks, millele see on suunatud.
DFS-i rakendused
Siin on DFS-i olulised rakendused:
Kaalutud graafik:
Kaalutud graafil genereerib DFS-i graafi läbimine lühima teepuu ja minimaalse läbipuu.
Tsükli tuvastamine graafikul:
Graafikul on tsükkel, kui DFS-i käigus leidsime tagumise serva. Seetõttu peaksime graafiku jaoks käivitama DFS-i ja kontrollima tagumiste servade olemasolu.
Raja leidmine:
Me võime spetsialiseeruda DFS-i algoritmile, et otsida teed kahe tipu vahel.
Topoloogiline sortimine:
Seda kasutatakse peamiselt töökohtade ajastamiseks etteantud sõltuvustest sõltuvalt töökohtade rühmast. Arvutiteaduses kasutatakse seda käskude ajastamisel, andmete järjestamisel, loogikasünteesil, kompileerimisülesannete järjekorra määramisel.
Graafiku tugevalt ühendatud komponentide otsimine:
Seda kasutati DFS-graafikus, kui graafiku igast tipust on tee ülejäänud ülejäänud tippudeni.
Mõistatuste lahendamine ainult ühe lahendusega:
DFS-i algoritmi saab hõlpsasti kohandada kõigi labürindi lahenduste otsimiseks, lisades külastatud komplekti olemasolevale teele ka sõlmed.
PÕHISED VAHED:
- BFS leiab lühima tee sihtkohta, samas kui DFS läheb alampuu põhja, seejärel pöördub tagasi.
- BFS-i täielik vorm on laiuse esimene otsing, samas kui DFS-i täielik vorm on sügava esimese otsing.
- BFS kasutab järgmise külastatava asukoha jälgimiseks järjekorda. arvestades, et DFS kasutab virna järgmise külastatava asukoha jälgimiseks.
- BFS läbib puu taseme järgi, DFS aga puu sügavuse järgi.
- BFS rakendatakse FIFO loendi abil, teisalt aga DFS rakendatakse LIFO loendi abil.
- BFS-is ei saa te kunagi olla piiratud piiratud silmustes, samas kui DFS-is võite olla lõpututes silmustes.