BFS vs DFS – ero niiden välillä

Mikä on BFS?

BFS on algoritmi, jota käytetään datan kuvaamiseen tai puuhakuun tai rakenteiden läpikulkuun. Algoritmi vierailee ja merkitsee tehokkaasti kaikki graafin avainsolmut tarkasti leveyssuunnassa.

Tämä algoritmi valitsee yhden solmun (alku- tai lähdepisteen) kaaviosta ja vierailee sitten kaikissa valitun solmun vieressä olevissa solmuissa. Kun algoritmi vierailee ja merkitsee aloitussolmun, se siirtyy kohti lähimpiä vierailemattomia solmuja ja analysoi ne.

Kun olet käynyt, kaikki solmut on merkitty. Nämä iteraatiot jatkuvat, kunnes kaikki kaavion solmut on käyty ja merkitty onnistuneesti. BFS:n täysi muoto on Breadth-first-haku.

Mikä on DFS?

DFS on algoritmi graafien tai puiden löytämiseen tai läpikäymiseen syvyyssuunnassa. Algoritmin suoritus alkaa juurisolmusta ja tutkii jokaisen haaran ennen paluuta.trackuningas. Se käyttää pinotietorakennetta muistaakseen, hakeakseen seuraavan solmun ja aloittaakseen haun aina, kun umpikujaan tulee missä tahansa iteraatiossa. DFS:n täydellinen muoto on syvyyshaku.

Ero BFS:n ja DFS:n binaaripuun välillä

Tässä ovat tärkeät erot BFS:n ja DFS:n välillä.

BFS	DFS
BFS löytää lyhimmän polun määränpäähän.	DFS palaa alipuun pohjalle ja sitten takaisintracks.
BFS:n täysi muoto on Breadth-First Search.	DFS:n täysi muoto on Depth First Search.
Se käyttää jonoa pitääkseen track seuraavasta vierailukohteesta.	Se käyttää pinoa pitääkseen track seuraavasta vierailukohteesta.
BFS kulkee puun tason mukaan.	DFS kulkee puun syvyyden mukaan.
Se toteutetaan FIFO-listalla.	Se toteutetaan LIFO-luettelon avulla.
Se vaatii enemmän muistia verrattuna DFS:ään.	Se vaatii vähemmän muistia BFS:ään verrattuna.
Tämä algoritmi antaa matalimman polun ratkaisun.	Tämä algoritmi ei takaa matalinta polkuratkaisua.
Selkää ei tarvitatrackuningas BFS:ssä.	Takaa on tarpeentrackuningas DFS:ssä.
Et voi koskaan jäädä rajallisiin silmukoihin.	Voit jäädä loukkuun loputtomiin silmukoihin.
Jos et löydä tavoitetta, saatat joutua laajentamaan monia solmuja ennen kuin ratkaisu löytyy.	Jos et löydä mitään tavoitetta, lehtisolmu palaa takaisintrackuningas voi esiintyä.

Esimerkki BFS:stä

Seuraavassa BFS-esimerkissä olemme käyttäneet graafia, jossa on 6 kärkeä.

Esimerkki BFS:stä

Vaihe 1)

Sinulla on kaavio, jossa on seitsemän numeroa välillä 0–6.

Vaihe 2)

0 tai nolla on merkitty juurisolmuksi.

Vaihe 3)

0 käy, merkitään ja lisätään jonotietorakenteeseen.

Vaihe 4)

Loput 0 vierekkäistä ja vierailematonta solmua käydään, merkitään ja lisätään jonoon.

Vaihe 5)

Ajoiteraatioita toistetaan, kunnes kaikki solmut on käyty.

Esimerkki DFS:stä

Seuraavassa DFS-esimerkissä olemme käyttäneet suuntaamatonta graafia, jossa on 5 kärkeä.

Vaihe 1)

Olemme aloittaneet kärjestä 0. Algoritmi alkaa laittamalla se vierailtuun listaan ​​ja samanaikaisesti kaikki sen viereiset kärjet tietorakenne kutsutaan pinoksi.

Vaihe 2)

Vieraat elementissä, joka on pinon yläosassa, esimerkiksi 1, ja siirryt sen viereisiin solmuihin. Se johtuu siitä, että 0 on jo vieraillut. Siksi vierailemme kärjessä 2.

Vaihe 3)

Vertex 2:ssa on vierailematon lähipiste 4:ssä. Siksi lisäämme sen pinoon ja vierailemme siinä.

Vaihe 4)

Lopuksi vierailemme viimeisessä kärjessä 3, jossa ei ole vierailemattomia vierekkäisiä solmuja. Olemme suorittaneet graafin läpikäynnin DFS-algoritmilla.

BFS:n sovellukset

Tässä ovat BFS:n sovellukset:

Painottamattomat kaaviot

BFS-algoritmi voi helposti luoda lyhimmän polun ja vähimmäisvirittävän puun vieraillakseen graafin kaikissa pisteissä mahdollisimman lyhyessä ajassa suurella tarkkuudella.

P2P-verkot

BFS voidaan toteuttaa paikantamaan kaikki lähimmät tai viereiset solmut vertaisverkossa. Tämä löytää tarvittavat tiedot nopeammin.

Verkkoindeksointirobotit

Hakukoneet tai indeksointirobotit voivat helposti rakentaa useita indeksitasoja käyttämällä BFS:ää. BFS-toteutus alkaa lähteestä, joka on verkkosivu, ja sitten se vierailee kaikissa linkeissä kyseisestä lähteestä.

Verkkolähetys

BFS-algoritmi ohjaa lähetettyä pakettia etsimään ja saavuttamaan kaikki solmut, joille sillä on osoite.

DFS:n sovellukset

Tässä on tärkeitä DFS:n sovelluksia:

Painotettu kaavio

Painotetussa kaaviossa DFS-kuvaajan läpikäyminen luo lyhimmän polun puun ja pienimmän virittävän puun.

Syklin havaitseminen kaaviossa

Graafilla on sykli, jos löysimme takareunan DFS:n aikana. Siksi meidän pitäisi ajaa DFS kaaviolle ja tarkistaa takareunat.

Polun löytäminen

Voimme erikoistua DFS-algoritmiin etsimään polkua kahden kärjen välillä.

Topologinen lajittelu

Sitä käytetään ensisijaisesti töiden ajoittamiseen annetuista riippuvuuksista työryhmän kesken. Tietojenkäsittelytieteessä sitä käytetään ohjeiden ajoituksessa, tietojen serialisoinnissa, logiikkasynteesissä, käännöstehtävien järjestyksen määrittämisessä.

Kaavion vahvasti toisiinsa liittyvien komponenttien etsiminen

Sitä käytetään DFS-graafissa, kun jokaisesta graafin kärjestä on polku muihin jäljellä oleviin kärkipisteisiin.

Palapelien ratkaiseminen vain yhdellä ratkaisulla

DFS-algoritmi voidaan helposti mukauttaa etsimään kaikkia ratkaisuja sokkeloon sisällyttämällä solmuja olemassa olevalle polulle vierailltuun joukkoon.