Soovitatav, 2020

Toimetaja Valik

Erinevus BFS ja DFS vahel

Suurim erinevus BFS ja DFS vahel on see, et BFS jätkab taset tasemel, samal ajal kui DFS järgib kõigepealt teekonda, mis moodustab alguse lõppsõlme (tipu), seejärel teise tee algusest lõpuni ja nii edasi, kuni kõik sõlmed on külastatud. Lisaks kasutab BFS sõlmede talletamiseks järjekorda, samas kui DFS kasutab sõlmede läbisõiduks.

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
BFSDFS
PõhilineVertex-põhine algoritmServal põhinev algoritm
Andmestruktuur, mida kasutatakse sõlmede salvestamiseksJärjekordStack
Mälu tarbimineEbatõhusTõhus
Ehitatud puu ülesehitusLai ja lühikeKitsas ja pikk
Moodsa liikumineKõigepealt uuritakse vanimaid mitteteadlikke tippe.Alguses uuritakse servi piki vertikaale.
OptimaalsusOptimaalne, et leida lühim vahemaa, mitte maksumus.Ei ole optimaalne
RakendusUurib 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.

Rakendused-

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.

Taotlus-

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

  1. BFS on tipupõhine algoritm, samas kui DFS on servapõhine algoritm.
  2. BFSis kasutatakse järjekorraandmete struktuuri. Teisest küljest kasutab DFS stacki või rekursiooni.
  3. Mälu ruumi kasutatakse tõhusalt DFS-is, samas kui ruumi kasutamine BFS-is ei ole tõhus.
  4. BFS on optimaalne algoritm, kuid DFS ei ole optimaalne.
  5. 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.

Top