BFS ja DFS ovat molemmat elintärkeitä kuvaajalöydöksille. BFS tarkoittaa Breadth-First Search ja DFS tarkoittaa Depth-First Search. Molemmilla on ero kahden välillä. Molemmat käyttävät jopa erilaista tietorakennetta toiminnassa, toinen Jono-tietorakennetta ja toinen pinotietorakennetta.
BFS vs DFS
Suurin ero BFS:n ja DFS:n välillä on, että Breadth-First Search on huippupisteeseen perustuva tekniikka, joka auttaa osoittamaan kaavion lyhimmän polun. Toisaalta DFS eli Depth First Search on reunaan perustuva tekniikka. BFS on tekniikka, joka riippuu jonotietorakenteesta. Toisaalta DFS riippuu pinotietorakenteesta.
BFS on tekniikka, jota käytetään kaavion lyhimmän reitin selvittämiseen käyttämällä Queue-tietorakennetta. Se sopii pisteiden etsimiseen lähteen läheisiltä alueilta. Toisin kuin DFS, sitä ei voida paremmin soveltaa pulmapelien tai pelien päätöksentekopuihin.
DFS on tekniikka, jota käytetään kaavion lyhimmän polun selvittämiseen pinotietorakenteen avulla. Se sopii alueille, jotka ovat kaukana ratkaisun lähteistä. Toisin kuin BFS, sitä voidaan paremmin soveltaa päätöksentekoon tai pelien ongelmanratkaisuun.
Vertailutaulukko BFS:n ja DFS:n välillä
| Vertailuparametrit | BFS | DFS |
| Täysi muoto ja määritelmä | BFS on lyhenne sanoista Breadth-First Search. Se on huippupisteeseen perustuva tekniikka, jota käytetään kaavion lyhimmän reitin löytämiseen. | DFS on lyhenne sanoista Depth First Search. Se on reunoihin perustuva tekniikka kaavion lyhimmän reitin löytämiseksi. |
| Riippuvuus tietorakenteesta | Breadth-First Search eli BFS selvittää kaavion lyhimmän polun Queue-tietorakenteen avulla. | Depth First Search eli DFS selvittää kaavion lyhimmän polun pinotietorakenteen avulla. |
| Käyttää | Painottamattomassa graafissa sitä käytetään yksittäisen lähteen lyhimmän polun löytämiseen, koska se käyttää vähiten kärkilähteen reunoja. | DFS:ssä määränpään tai huippupisteen saavuttamiseksi mistä tahansa lähteestä enemmän reunoja tulisi kulkea läpi. |
| Soveltuvuusalue | Sen soveltuvuus pisteiden etsimiseen on lähteen lähietäisyydellä. Se ei sovellu pelien päätöspuiden tekemiseen. | Sen soveltuvuusalue vaihtelee kaukana lähteestä olevissa ratkaisuissa. Se sopii paremmin pelien tai pulmapelien päätöksentekoon tai ongelmiin. |
| Mekanismi | Tässä tekniikassa valitaan yksi piste kerrallaan sen käynnin aikana ja merkitään, minkä jälkeen viereisessä käydään ja varastoidaan jonoon. | Käydyt pisteet laitetaan pinoon ja sitten, jos niitä ei ole, vieraillut pisteet pompataan. |
Mikä on BFS?
BFS:n avulla graafia kuljetetaan leipänä kohti liikettä. Tässä tekniikassa käytetään jonoa, jotta muistaa hakea seuraava huippupiste. Tämä tapahtuu, kun se kohtaa umpikujan iteraatiossa. Sitä ei pidetä päätöspuina, koska se kattaa laajasti kaikki naapurit. Se on verrattain hidas kuin DFS. BFS-algoritmin BFS:n aikamonimutkaisuus on O(V+E) vierekkäisen listan aikana ja O(V^2) viereisyysmatriisin aikana. Tässä E tarkoittaa reunoja ja V tarkoittaa huippuja. Graafissa olevaa BFS-algoritmia voidaan käyttää eri aloilla.
BFS:ää käytetään paljon jokaisen naapurisolmun luomiseen vertaisyhteyksissä. Hakukoneen indeksointirobotit rakentavat hakemiston tämän tekniikan avulla. Lähdesivuilta uusiin sivuihin se auttaa löytämään kaikki siihen liittyvät linkit. Sitä tarvitaan naapuripaikkojen löytämiseen GPS-navigointitoiminnon avulla. BFS-algoritmia käytetään lähetettäessä joitain paketteja verkossa. Polunhakualgoritmi kattaa BFS:n. Tämän tekniikan avulla verkon suurin virtaus voidaan löytää Ford-Fulkerson-algoritmista.
Mikä on DFS?
DFS:n avulla graafia kuljetetaan syvyyssuuntaisessa liikkeessä. Pinoa käytetään tässä tekniikassa muistuttamaan pisteen saamisesta edellisen viereen. Haku tehdään minkä tahansa iteroinnin aikana. Päätöspuun aikana tulee tehdä lisää traversejä päätöksen vahvistamiseksi. Lopuksi voitto tunnustetaan. se on suhteellisen nopea nopeudeltaan kuin BFS. DFS:n aikamonimutkaisuus on O(V+E) viereisen listan aikana ja O(V^2) viereisen matriisin aikana. Tässä E tarkoittaa reunoja ja V tarkoittaa huippuja. DFS:ää käytetään laajasti eri aloilla.
Kun DFS suoritetaan painottamattomalle graafille, jokaiselle lyhimmälle polkupuuparille kehitetään vähimmäisvirittävät puut. Sitä voidaan soveltaa syklien tunnistamiseen kaavioissa. Jos yksi takareuna löytyy BFS:stä, on yksi sykli. Tämän tekniikan avulla voidaan löytää polku u:n ja v:n tai kahden kärjen välillä. DFS-algoritmia käytetään topologiseen lajitteluun. Sitä voidaan käyttää määrittämään komponentit, jotka ovat vahvasti linkitetty tietyssä graafissa. Komponentit on luotu olemaan vahvasti yhteydessä toisiinsa, kun kunkin kärjen välillä on polku.
Tärkeimmät erot BFS:n ja DFS:n välillä
Johtopäätös
Siten voidaan päätellä sanomalla, että BFS ja DFS eroavat selvästi toisistaan. BFS:ää käytetään graafissa lyhimmän polun etsimiseen jonotietorakenteen avulla ja DFS:ää graafissa lyhimmän polun löytämiseen pinotietorakenteen avulla. BFS valitsee käyntinsä aikana yhden huippupisteen, jonka jälkeen viereisessä käydään ja se kerätään jonoon. Toisaalta DFS:ssä vieraillut kärjet sisällytetään pinoon ja pisteiden puuttuessa kärkipisteet pompataan. BFS:n tekniikka perustuu vertexiin ja DFS:n reunaan.
