Mikä on BFS?
BFS on algoritmi, jota käytetään tietojen piirtämiseen tai puun tai liikkuvien rakenteiden etsimiseen. Algoritmi vierailee ja merkitsee tehokkaasti kaikki kaavion avainsolmut tarkasti leveydeltään.
Tämä algoritmi valitsee kaaviosta yhden solmun (alku- tai lähdekohdan) ja vierailee sitten kaikki valitun solmun vieressä olevat solmut. Kun algoritmi vierailee ja merkitsee aloitussolmun, se siirtyy kohti lähimpiä avaamattomia solmuja ja analysoi ne.
Vierailun jälkeen kaikki solmut on merkitty. Nämä iteraatiot jatkuvat, kunnes kaavion kaikki solmut on vierailtu ja merkitty onnistuneesti. BFS: n koko muoto on leveyshaku.
Tässä BSF vs. DFS-binaaripuun opetusohjelma, opit:
- Mikä on BFS?
- Mikä on DFS?
- Esimerkki BFS: stä
- Esimerkki DFS: stä
- Ero BFS: n ja DFS-binaaripuun välillä
- BFS: n sovellukset
- DFS: n sovellukset
Mikä on DFS?
DFS on algoritmi kuvaajien tai puiden etsimiseen tai kulkemiseen syvyyssuunnassa. Algoritmin toteutus alkaa juurisolmusta ja tutkii kutakin haaraa ennen paluuta. Se käyttää pinon tietorakennetta muistaa, saada seuraava kärki ja aloittaa haun aina, kun umpikuja esiintyy missä tahansa iteraatiossa. DFS: n koko muoto on syvyyshaku.
Esimerkki BFS: stä
Seuraavassa DFS-esimerkissä olemme käyttäneet kuvaajaa, jossa on 6 kärkeä.
Esimerkki BFS: stä
Vaihe 1)
Sinulla on kaavio seitsemästä luvusta, jotka vaihtelevat välillä 0-6.
Vaihe 2)
0 tai nolla on merkitty juurisolmuksi.
Vaihe 3)
0 on käynyt, merkitty ja lisätty jonotietorakenteeseen.
Vaihe 4)
Jäljellä olevissa 0 vierekkäisessä ja käymättömässä solmussa käydään, merkitään ja lisätään jonoon.
Vaihe 5)
Liikkuvia iteraatioita toistetaan, kunnes kaikissa solmuissa käydään.
Esimerkki DFS: stä
Seuraavassa DFS-esimerkissä olemme käyttäneet suuntaamatonta kuvaajaa, jossa on 5 kärkeä.
Vaihe 1)
Olemme aloittaneet huipusta 0. Algoritmi aloitetaan asettamalla se vierailulistalle ja asettamalla kaikki vierekkäiset pisteet samanaikaisesti pino-nimiseen tietorakenteeseen.
Vaihe 2)
Vierailet elementissä, joka on pinon yläosassa, esimerkiksi 1, ja mene sen vierekkäisiin solmuihin. Se johtuu siitä, että 0 on jo käynyt. Siksi vierailemme kärjessä 2.
Vaihe 3)
Vertex 2: lla on vierailematon lähellä oleva kärkipiste 4. Siksi lisäämme sen pinoon ja vierailemme siinä.
Vaihe 4)
Lopuksi käymme viimeisessä kärkipisteessä 3, sillä siinä ei ole vierailemattomia vierekkäisiä solmuja. Kaavion läpikäynti on suoritettu DFS-algoritmilla.
Ero BFS: n ja DFS-binaaripuun välillä
| BFS | DFS |
| BFS löytää lyhimmän polun määränpäähän. | DFS siirtyy alipuun alaosaan ja palaa sitten takaisin. |
| BFS: n koko muoto on Breadth-First Search. | DFS: n koko muoto on Depth First Search. |
| Se käyttää jonoa seuratakseen seuraavaa sijaintia. | Se käyttää pinoa seuraamaan seuraavaa vierailukohtaa. |
| BFS kulkee puutason mukaan. | DFS kulkee puun syvyyden mukaan. |
| Se toteutetaan FIFO-luettelon avulla. | Se toteutetaan käyttämällä LIFO-luetteloa. |
| Se vaatii enemmän muistia verrattuna DFS: ään. | Se vaatii vähemmän muistia kuin BFS. |
| Tämä algoritmi antaa matalin reitin ratkaisun. | Tämä algoritmi ei takaa matalin reitin ratkaisua. |
| BFS: ssä ei tarvitse palata takaisin. | DFS: ssä on palattava takaisin. |
| Et voi koskaan olla loukussa äärellisiin silmukoihin. | Voit olla loukussa äärettömiin silmukoihin. |
| Jos et löydä tavoitetta, sinun on ehkä laajennettava monia solmuja ennen ratkaisun löytämistä. | Jos et löydä tavoitetta, lehtisolmu voi palata takaisin. |
BFS: n sovellukset
Tässä ovat BFS: n sovellukset:
Painottamattomat kaaviot:
BFS-algoritmi voi helposti luoda lyhimmän polun ja pienimmän ulottuvuuspuun vierailemaan kaavion kaikissa pisteissä mahdollisimman lyhyessä ajassa suurella tarkkuudella.
P2P-verkot:
BFS voidaan toteuttaa paikantamaan kaikki lähimmät tai vierekkäiset solmut vertaisverkossa. Tämä löytää tarvittavat tiedot nopeammin.
Web-indeksoijat:
Hakukoneet tai indeksointirobotit voivat helposti luoda useita hakemistotasoja käyttämällä BFS: ää. BFS-toteutus alkaa lähteestä, joka on verkkosivu, ja sitten se vierailee kaikki kyseisen lähteen linkit.
Verkon lähetys:
Lähetettyä pakettia ohjaa BFS-algoritmi etsimään ja saavuttamaan kaikki solmut, joille se on osoitettu.
DFS: n sovellukset
Tässä ovat tärkeät DFS-sovellukset:
Painotettu kaavio:
Painotetussa kaaviossa DFS-kaavion läpikäynti luo lyhimmän polun ja pienimmän kattavan puun.
Syklin tunnistaminen kaaviosta:
Kaaviossa on sykli, jos löysimme takareunan DFS: n aikana. Siksi meidän on suoritettava kaavion DFS ja tarkistettava takareunat.
Polun etsiminen:
Voimme erikoistua DFS-algoritmiin etsimään polkua kahden kärjen välillä.
Topologinen lajittelu:
Sitä käytetään ensisijaisesti töiden ajoitukseen annetuista riippuvuuksista riippuen työpaikkaryhmästä. Tietojenkäsittelytieteessä sitä käytetään käskyjen ajoituksessa, tietojen sarjallisuudessa, logiikan synteesissä, kokoamistehtävien järjestyksen määrittämisessä.
Kaavion vahvasti yhdistettyjen komponenttien etsiminen:
Sitä käytettiin DFS-kaaviossa, kun kaavion jokaisesta pisteestä on polku muihin jäljellä oleviin pisteisiin.
Palapelien ratkaiseminen vain yhdellä ratkaisulla:
DFS-algoritmi voidaan helposti mukauttaa etsimään kaikkia labyrintin ratkaisuja sisällyttämällä solmut olemassa olevaan polkuun vierailemassa joukossa.
AVAINEROT:
- BFS löytää lyhimmän polun määränpäähän, kun taas DFS menee osapuun pohjaan ja palaa sitten takaisin.
- BFS: n koko muoto on Breadth-First Search, kun taas DFS: n koko muoto on Depth First Search.
- BFS seuraa jonoa seuraamaan seuraavaa sijaintia. kun taas DFS käyttää pinoa seuraamaan seuraavaa paikkaa, jossa vierailet.
- BFS kulkee puun tason mukaan, kun taas DFS kulkee puun syvyyden mukaan.
- BFS toteutetaan käyttämällä FIFO-luetteloa ja toisaalta DFS toteutetaan käyttämällä LIFO-luetteloa.
- BFS: ssä et voi koskaan olla loukussa äärellisiin silmukoihin, kun taas DFS: ssä voit olla loukussa äärettömiin silmukoihin.