Ero BFS VS DFS: n välillä
Leveys-ensimmäinen haku (BFS) ja ensimmäisen syvyyden haku (DFS) ovat kaksi tärkeää algoritmia, joita käytetään hakuun. Leveys ensimmäinen haku aloittaa haun ensimmäisestä solmusta ja siirtyy sitten tasojen yli, jotka ovat lähempänä juurisolmua, kun taas Syvyys ensimmäisen haun algoritmi alkaa ensimmäisellä solmulla ja suorittaa sitten polunsa vastaavan polun loppusolmuun. Molemmat algoritmit kulkevat jokaisen solmun läpi etsinnän aikana. Kahdelle algoritmille kirjoitetaan erilaisia koodeja kulkemisprosessin suorittamiseksi. Niitä pidetään myös tärkeinä keinotekoisen älykkyyden hakualgoritmeina.
Tässä aiheessa aiomme oppia BFS VS DFS: stä.
Kuinka BFS ja DFS toimivat?
Molempien algoritmien toimintamekanismi selitetään alla esimerkkeinä. Ole hyvä ja katso heitä ymmärtämään paremmin käytettyä lähestymistapaa.
Leveys-ensimmäinen hakuesimerkki
- Vaihe 1: N1 on juurisolmu, joten se alkaa tästä. N1 on kytketty kolmeen solmuun N2, N3 ja N4. Kaikkia kolmea solmua ei ole vielä käyty. Joten aloitamme N2: sta ja säilytämme sitä jonossa. Joten Q-jonossa on vain N2.
Q: N2
- Vaihe 2: Seuraava solmu, joka on yhdistetty N1: ään, on N3. Koska olemme käyneet solmun yli tai käyneet siellä, tallennamme sen jonoon. Joten, päivitetty jono on
Q: N3, N2
- Vaihe 3: Seuraavaksi juurisolmuun kytketty solmu on N4. Tallennamme sen jonossa.
Q: N4, N3, N2
- Vaihe 4: Kaikki solmuihin, jotka on kytketty N1: ään, tallennetaan jonoon. Nyt poistamme N2 jonosta ensimmäisen FIFO-periaatteen mukaisesti ja löydä solmut, jotka on kytketty N2: ään eli N5. N5: llä ei käydä kerran, joten säilytämme sen jonossa.
Q: N5, N4, N3
- Vaihe 5: Kaikkia huipuja käydään, joten jatkamme solmujen poistamista jonosta, kunnes se on tyhjä.
Ensimmäinen syvyyshaku Esimerkki
- Vaihe 1: Aloitamme N1: llä aloitussolmuna ja tallenna se pinoon S. N1 on kytketty kolmeen viereiseen solmuun N2, N3 ja N4. Alkaen N2: lta (voit aloittaa aakkosjärjestyksessä tai numeerisesti), laitamme tämän pinoon.
S: N2 (yläosa), N1
- Vaihe 2: N2 : n vierekkäiset solmut ovat nyt N1 ja N5. Koska N1 on jo läsnä pinossa, se tarkoittaa sitä, että vieraillaan, joten otamme N5 ja laitamme sen pinoon S.
S: N5 (yläosa), N2, N1
- Vaihe 3: N5 : n vierekkäiset solmut ovat nyt N3 ja N4. Aloitamme N3 ja laitamme sen pinoon.
S: N3 (yläosa), N5, N2, N1
N3 on nyt kytketty N5: ään ja N1: ään, jotka ovat jo mukana pinossa, mikä tarkoittaa, että vieraillaan, joten poistamme N3: n pinosta LIFO (Last in First Out) -periaatteen mukaisesti.
S: N5 (yläosa), N2, N1
- Vaihe 4: Laitamme nyt viimeisen solmun, jota emme törmänneet koko N4: n läpi kulkevaan kohtaan, ja laitamme sen pinoon.
S: N4 (yläosa), N5, N2, N1
- Vaihe 5: Nyt meitä ei jätetä muiden solmujen ulkopuolelle, joten tarkistamme pinossa, onko siinä oleviin vastaaviin solmuihin kytketty solmuja, joita ei käytetä. Jos kaikkia kytkettyjä solmuja käydään, poistamme pinossa olevat solmut. Esimerkiksi N4: llä ei ole kytkentäsolmuja, joita emme tarkistaneet, joten poistamme sen pinosta. Samoin voimme tarkistaa muita solmuja. Algoritmi pysähtyy, kun pino on tyhjä.
Head to Head -vertailu BFS VS DFS: n (infografia) välillä
Alla on 6 parasta eroa BFS VS DFS: n välillä
Keskeiset erot BFS: n ja DFS: n välillä
Keskustelemme joistain tärkeimmistä eroista BFS: n ja DFS: n välillä
- Leveys-ensimmäinen haku (BFS) alkaa juurisolmusta ja käy kaikkiin siihen liitettyihin vastaaviin solmuihin, kun taas DFS alkaa juurisolmusta ja suorittaa solmuun liitetyn koko polun.
- BFS noudattaa jonon lähestymistapaa, kun taas DFS seuraa pinoa.
- BFS: ssä käytetty lähestymistapa on optimaalinen, kun taas DFS: ssä käytetty prosessi ei ole optimaalinen.
- Jos tavoitteemme on löytää lyhin polku, kuin BFS on parempi kuin DFS.
BFS: n ja DFS: n vertailutaulukko
Keskustelemme parhaasta vertailusta BFS: n ja DFS: n välillä
| BFS | DFS |
| BFS: n koko muoto on ensimmäinen leveyshaku. | DFS: n koko muoto on Depth First Search |
| BFS: n on tarkoitus löytää lyhin etäisyys ja se alkaa ensimmäisestä tai juurisolmusta ja liikkuu kaikkien sen solmujen läpi, jotka on kiinnitetty vastaaviin solmuihin. Saat selkeän kuvan sen toimintamekanismista, kun olet käynyt läpi alla olevan esimerkin. | DFS noudattaa syvyysperusteista lähestymistapaa ja se suorittaa täydellisen polun kaikkien vastaavaan solmuun kiinnitettyjen solmujen läpi. Voit saada selkeän kuvan sen toimintamekanismista käymällä läpi alla oleva esimerkki. |
| Se tehdään jonoperiaatteella, joka on FIFO (First In First Out) -lähestymistapa. | Se tehdään käyttämällä pino-periaatetta, joka on viimeinen sisään -lähestymistapa (LIFO). |
| Useamman kerran kulkevat solmut poistetaan jonosta. | Käytetyt solmut lisätään pinoon ja myöhemmin, jos vierailevia solmuja ei ole enää, ne poistetaan. |
| Se on suhteellisen hitaampi kuin Depth First Search. | Se on nopeampi kuin leveys ensin -algoritmi. |
| Muistin allokointi on enemmän kuin Depth First Search -algoritmi. | Muistin allokointi on verrattain pienempi kuin ensimmäisen leveyden hakualgoritmi |
johtopäätös
On monia sovelluksia, joissa yllä olevia algoritmeja käytetään koneoppimisina tai keinotekoiseen älykkyyteen liittyvien ratkaisujen löytämiseen jne. Niitä käytetään pääasiassa kaavioissa, jotta löydettäisiin onko se kaksipuolinen vai ei, havaitakseen kytketyt syklit tai komponentit. Niitä pidetään myös tärkeinä algoritmeina polun tai lyhimmän etäisyyden löytämisessä. Yrityksen vaatimuksista riippuen voimme käyttää kahta algoritmia. Leveys-ensimmaista hakua pidetään kuitenkin optimaalisena tapana kuin syvyyden ensimmäisen haun algoritmi.
Suositellut artikkelit
Tämä on opas BFS VS DFS: ään. Tässä keskustellaan BFS VS DFS: n avaineroista infografian ja vertailutaulukon kanssa. Saatat myös katsoa seuraavia artikkeleita saadaksesi lisätietoja -
- BFS-algoritmi
- TeraData vs. Oracle
- Big Data vs. Data Warehouse
- Big Data vs. Apache Hadoop: 4 suosituinta vertailua, joka sinun on opittava