BFS vs. DFS
Sisältö
- Sisältö: Ero BFS: n ja DFS: n välillä
- Vertailutaulukko
- BFS
- DFS
- Keskeiset erot
- johtopäätös
- Selittävä video
Ero BFS: n, joka on leveys ensin, ja DFS: n, joka on syvyys ensin, välillä on se, että leveys ensin on graafin kulkemismenetelmä, joka käyttää jonoa vierailtujen pisteiden tallentamiseen, kun taas syvyys ensimmäinen haku on kuvaajaa kulkeva menetelmä, joka käyttää pinoa. vierailtujen kärkipisteiden tallentamiseksi.
Hengitys ensimmäinen haku ja syvä ensin haku ovat tärkeimpiä käsitteitä tietokoneohjelmoinnissa. Syvyyshaku seuraa polkua alusta loppuun, joka on loppusolmu toisaalta leivän ensimmäinen hakutyö tasolta. Jos puhumme pääerosta, niin tärkein ero BFS: n, joka on leveys ensimmäinen haku, ja DFS: n, joka on syvyys ensin -haun välillä, on, että leveyden ensimmäinen haku on kuvaajan kulkemismenetelmä, joka käyttää jonoa vierailtujen pisteiden tallentamiseen, kun taas syvyys-ensimmäinen haku on kuvaajan kulkemismenetelmä, joka käyttää pinoa vierailtujen pisteiden tallentamiseen. Leveys-ensimmäinen haku, jota kutsutaan pian BFS: ksi, BFS: tä käytetään kulkemaan kuvaajan läpi. Jonoa käytetään tallennettujen pisteiden tallentamiseen BFS: ään. BFS toimii kärkipisteissä, vierailut kärjet tallennetaan jonoon. Huiput tallennetaan yksitellen. Jokainen kuvaajan solmu tutkitaan täysin, ja sitten käydään kuvaajan muita huippuja.
Syvyys Ensimmäinen haku, joka tunnetaan nimellä DFS, on myös kuvaajan kulkemismenetelmä, jossa pinoa käytettiin kärkien tallentamiseen. Leveys-ensimmäinen haku ei ole reunapohjainen menetelmä, kun taas syvyys-ensimmäinen haku on reunapohjainen menetelmä. Ensimmäinen syvyyshaku toimii rekursiivisella tavalla, jossa kärkiä tutkitaan reunojen läpi. Ensimmäisessä syvähaussa kutakin kärkipistettä käydään kerran, joka tarkistetaan kahdesti.
Sisältö: Ero BFS: n ja DFS: n välillä
- Vertailutaulukko
- BFS
- DFS
- Keskeiset erot
- johtopäätös
- Selittävä video
Vertailutaulukko
Perusta | BFS | DFS |
merkitys | Leveys ensimmäinen haku on kuvaajan kulkemismenetelmä, joka käyttää jonoa vierailtujen kärkipisteiden tallentamiseen | Syvyyshaku on graafin kulkemismenetelmä, joka käyttää pinoa vierailtujen kärkipisteiden tallentamiseen. |
algoritmi | Leveys ensimmäinen haku on kärkipohjainen algoritmi | Ensimmäinen syvyyshaku on reunapohjainen algoritmi |
Muisti | Leveys ensimmäinen haku on tehoton muistia | Ensimmäinen syvyyshaku on muistitehokas |
hakemus | Tutkii kaksiosaista kuvaajaa, kytkettyä komponenttia ja kaavion läsnä olevaa lyhintä tietä. | Tutkii kahden reunan kytkettyä kuvaajaa, kiinteästi kytkettyä kuvaajaa, asyklistä kuvaajaa ja topologista järjestystä. |
BFS
Leveys-ensimmäinen haku, jota kutsutaan pian BFS: ksi, BFS: tä käytetään kulkemaan kuvaajan läpi. Jonoa käytetään tallennettujen pisteiden tallentamiseen BFS: ään. BFS toimii kärkipisteissä, vierailut kärjet tallennetaan jonoon. Huiput tallennetaan yksitellen. Jokaista kuvaajan solmua tutkitaan täysin, ja sitten käydään kuvaajan muita huippuja. Leveys-ensimmäistä hakua käytetään selvittämään, onko kaavio kytketty vai ei. Leveys-ensimmäistä hakua käytetään kaksipuolisen kuvaajan havaitsemiseen. Lyhyimmät polut löytyvät käyttämällä BFS: ää.
DFS
Syvyys Ensimmäinen haku, joka tunnetaan nimellä DFS, on myös kuvaajan kulkemismenetelmä, jossa pinoa käytettiin kärkien tallentamiseen. Leveys-ensimmäinen haku ei ole reunapohjainen menetelmä, kun taas syvyys-ensimmäinen haku on reunapohjainen menetelmä.Ensimmäinen syvyyshaku toimii rekursiivisella tavalla, jossa kärkiä tutkitaan reunojen läpi. Ensimmäisessä syvähaussa jokainen kärki käydään kerran, joka tarkistetaan kahdesti.
Keskeiset erot
- Leveys-ensimmäinen haku on kuvaajan kulkemismenetelmä, joka käyttää jonoa vierailtujen kärkipisteiden tallentamiseen, kun taas Syvyyden ensimmäinen haku on kuvaajan kulkumenetelmä, joka käyttää pinoa vierailtujen pisteiden tallentamiseen.
- Leveys-ensimmäinen haku on kärkipohjainen algoritmi, kun taas Syvyys-ensimmäinen haku on reunapohjainen algoritmi
- Leveys-ensimmäinen haku on muistin tehoton, kun taas syvyys-ensimmäinen haku on muistin tehokas.
- Tutkii kaksiosaista kuvaajaa, kytkettyä komponenttia ja kaavion läsnä olevaa lyhintä tietä, kun taas tarkastelee kaksireunaista kytkettyä kuvaajaa, voimakkaasti kytkettyä kuvaajaa, asyklistä kuvaajaa ja topologista järjestystä.
johtopäätös
Tässä yllä olevassa artikkelissa näemme selvän eron hengityksen ensimmäisen haun ja ensin syvähaun välillä toteutuksen kanssa.