BFS ja DFS on graafiku otsimisel kasutatavad läbivusmeetodid. Graafi liikumine on graafiku kõigi sõlmede külastamise protsess. Graafik on vertikaalide 'V' ja tippude E ühendavate servade rühm.
Võrdluskaart
| Võrdluse alus | BFS | DFS |
|---|---|---|
| Põhiline | Vertex-põhine algoritm | Serval põhinev algoritm |
| Andmestruktuur, mida kasutatakse sõlmede salvestamiseks | Järjekord | Stack |
| Mälu tarbimine | Ebatõhus | Tõhus |
| Ehitatud puu ülesehitus | Lai ja lühike | Kitsas ja pikk |
| Moodsa liikumine | Kõigepealt uuritakse vanimaid mitteteadlikke tippe. | Alguses uuritakse servi piki vertikaale. |
| Optimaalsus | Optimaalne, et leida lühim vahemaa, mitte maksumus. | Ei ole optimaalne |
| Rakendus | Uurib kahepoolset graafi, ühendatud komponenti ja lühimat rada graafikus. | Uurib kahe servaga ühendatud graafi, tugevalt ühendatud graafi, atsüklilist graafikut ja topoloogilist järjestust. |
BFSi määratlus
Esimene otsing (BFS) on graafides kasutatav liikumismeetod. Ta kasutab külastatud tippude salvestamiseks järjekorda. Selle meetodi puhul on rõhk graafiku tippudel, esimesel juhul valitakse üks tipp, seejärel külastatakse ja märgistatakse. Seejärel külastatakse külastatud tipuga külgnevaid tippe ja hoitakse neid järjekorras järjekorras. Samamoodi töödeldakse salvestatud tipusid ükshaaval ja nende külgnevad tipud külastatakse. Enne mis tahes teise graafiku sõlme külastamist uuritakse täielikult sõlme, see tähendab, et see läbib kõigepealt kõige vähem uurimata sõlme.
Näide
Meil on graafik, mille tipud on A, B, C, D, E, F, G. Arvestades A lähtepunktina. Protsessi etapid on järgmised:
- Vertex A laiendatakse ja salvestatakse järjekorda.
- A vertikaale B, D ja G laiendatakse ja hoitakse järjekorras Vertex A eemaldatud.
- Nüüd eemaldatakse B järjekorra esiküljel koos järgmiste tippude E ja F salvestamisega.
- Vertex D on järjekorra esiküljel ja selle ühendatud sõlme F on juba külastatud.
- Vertex G eemaldatakse järjekorrast ja tal on järeltulija E, mida on juba külastatud.
- Nüüd eemaldatakse E-st ja F-st järjekord ning selle järeltulija C läbib ja salvestatakse järjekorda.
- Viimasel C-l on ka eemaldatud ja järjekord on tühi, mis tähendab, et oleme valmis.
- Loodud väljund on A, B, D, G, E, F, C.
BFS võib olla kasulik leidmaks, kas graafikul on ühendatud komponendid või mitte. Samuti saab seda kasutada kahepoolse graafiku tuvastamiseks.
Graaf on kahepoolne, kui graafiku tipud jagatakse kaheks lahutatud kogumiks; samas komplektis ei asu ühtegi kahte külgnevat tippu. Teine meetod kahepoolse graafiku kontrollimiseks on kontrollida paaritu tsükli esinemist graafikus. Kahesuunaline graaf ei tohi sisaldada paaritu tsüklit.
BFS on ka parem leida kõige lühem tee graafikus, mida võib vaadelda kui võrku.
DFS-i määratlus
Esimese otsingu sügavuse (DFS) läbimise meetod kasutab külastatavate tipude salvestamiseks virna. DFS on servapõhine meetod ja töötab rekursiivsel moel, kus tipud uuritakse mööda rada (serva). Sõlme uurimine peatatakse niipea, kui leitakse teine uurimata sõlme ja kõige sügavamate uurimata sõlmede läbimine. DFS läbib / külastab iga tipu täpselt üks kord ja iga serva kontrollitakse täpselt kaks korda.
Näide
Sarnaselt BFS-ile saab DFS-toimingute tegemiseks teha sama graafiku ja kaasatud sammud on järgmised:
- Arvestades A kui lähtepunkti, mida uuritakse ja hoitakse virnas.
- B järjestikuse tipu A salvestatakse virna.
- Vertex B-l on kaks järeltulijat E ja F, nende hulgas tähestikulises järjekorras E uuritakse ja salvestatakse virna.
- Versiooni E järeltulija, st G on salvestatud virna.
- Vertex G-l on kaks ühendatud tippu ja mõlemad on juba külastatud, nii et G on stäkist välja.
- Samamoodi eemaldati ka E s.
- Nüüd on tipus B virna ülaosas, selle teine sõlme (tipp) F uuritakse ja salvestatakse virna.
- Vertex F-l on kaks C- ja D-järeltulijat, nende vahel C liigub esmalt ja salvestatakse virna.
- Vertex C-l on ainult üks eelkäija, mida on juba külastatud, nii et see eemaldatakse virnast.
- Nüüd külastatakse F-ga ühendatud tippu D ja seda hoitakse virnas.
- Kuna tipus D puuduvad avastamata sõlmed, siis D eemaldatakse.
- Samamoodi ilmuvad ka F, B ja A.
- Loodud väljund on A, B, E, G, F, C, D.
DFS-i rakendused hõlmavad kahe servaga ühendatud graafi, tugevalt ühendatud graafi, atsüklilise graafi ja topoloogilise järjestuse kontrollimist .
Graafikut nimetatakse kaheks servaks, mis on ühendatud ainult siis, kui need jäävad ühendatuks isegi siis, kui üks selle servadest on eemaldatud. See rakendus on väga kasulik arvutivõrkudes, kus võrgu ühe lingi rike ei mõjuta ülejäänud võrku ja see oleks ikka veel ühendatud.
Tugevalt ühendatud graaf on graafik, milles peab olema tee tellitud tipude paari vahel. DFS-i kasutatakse suunatud graafis iga tellitud paari vahelise tee otsimiseks. DFS saab lahendada ühendusvõimalusi.
Peamised erinevused BFS ja DFS vahel
- BFS on tipupõhine algoritm, samas kui DFS on servapõhine algoritm.
- BFSis kasutatakse järjekorraandmete struktuuri. Teisest küljest kasutab DFS stacki või rekursiooni.
- Mälu ruumi kasutatakse tõhusalt DFS-is, samas kui ruumi kasutamine BFS-is ei ole tõhus.
- BFS on optimaalne algoritm, kuid DFS ei ole optimaalne.
- DFS konstrueerib kitsad ja pikad puud. Vastupidiselt BFS konstrueerib lai ja lühike puu.
Järeldus
BFS ja DFS, mõlemad graafi otsimise tehnikad, on sarnane tööaeg, kuid erinev ruumi tarbimine, DFS võtab lineaarset ruumi, sest me peame meeles pidama üksikut teed uurimata sõlmedega, samas kui BFS hoiab iga sõlme mälus.
DFS annab sügavamaid lahendusi ja ei ole optimaalne, kuid see toimib hästi, kui lahendus on tihe, samas kui BFS on optimaalne, mis otsib alguses optimaalset eesmärki.
