Mielőtt megvizsgálnánk a BFS és a DFS közötti különbségeket, először külön kell ismernünk a BFS-t és a DFS-t.
Mi az a BFS?
BFS jelentése Breadth First Search . Úgy is ismert, mint szintű rendelés bejárás . A Queue adatstruktúra a Breadth First Search bejáráshoz használatos. Ha egy gráfban a BFS algoritmust használjuk a bejáráshoz, bármely csomópontot tekinthetünk gyökércsomópontnak.
Tekintsük az alábbi grafikont az első szélességi keresés bejárására.
java szűrő folyam
Tegyük fel, hogy a 0-s csomópontot gyökércsomópontnak tekintjük. Ezért a bejárás a 0 csomóponttól indulna.
Ha a 0-s csomópontot eltávolítja a sorból, a rendszer kinyomtatja, és a jelzéssel látja el meglátogatott csomópont.
Ha a 0. csomópont eltávolításra kerül a sorból, akkor a 0. csomópont szomszédos csomópontjai bekerülnek egy sorba, az alábbiak szerint:
Most az 1-es csomópont eltávolításra kerül a sorból; a rendszer kinyomtatja és látogatott csomópontként jelöli meg
Amint az 1. csomópont eltávolításra kerül a sorból, az 1. csomópont összes szomszédos csomópontja hozzáadódik egy sorhoz. Az 1. csomópont szomszédos csomópontjai a 0, 3, 2, 6 és 5. De csak a nem látogatott csomópontokat kell beszúrnunk egy sorba. Mivel a 3., 2., 6. és 5. csomópont nem látogatott; ezért ezek a csomópontok egy sorba kerülnek az alábbiak szerint:
A következő csomópont a 3. egy sorban. Tehát a 3. csomópont eltávolításra kerül a várólistából, kinyomtatja és meglátogatottként jelöli meg az alábbiak szerint:
Miután a 3. csomópont eltávolításra kerül a sorból, a 3. csomópont összes szomszédos csomópontja a meglátogatott csomópontok kivételével hozzáadódik egy sorhoz. A 3. csomópont szomszédos csomópontjai a 0, 1, 2 és 4. Mivel a 0, 1 csomópontok már meg vannak látogatva, és a 2. csomópont jelen van egy várólistában; ezért csak a 4-es csomópontot kell beszúrnunk egy sorba.
fájl megnyitása java-ban
Most a sor következő csomópontja a 2. Tehát 2 törlődik a sorból. A rendszer kinyomtatja és látogatottként jelöli meg az alábbiak szerint:
Miután a 2. csomópont eltávolításra kerül a sorból, a 2. csomópont összes szomszédos csomópontja a meglátogatott csomópontok kivételével hozzáadódik egy sorhoz. A 2. csomópont szomszédos csomópontjai az 1, 3, 5, 6 és 4. Mivel az 1. és 3. csomópontot már meglátogatták, és a 4, 5, 6 már felkerült a sorba; ezért nem kell csomópontot beszúrnunk a sorba.
A következő elem az 5. Tehát az 5 törlődik a sorból. A rendszer kinyomtatja és látogatottként jelöli meg az alábbiak szerint:
Amint az 5. csomópont eltávolításra kerül a sorból, az 5. csomópont összes szomszédos csomópontja a meglátogatott csomópontok kivételével hozzáadódik a sorhoz. Az 5. csomópont szomszédos csomópontjai 1 és 2. Mivel mindkét csomópontot már meglátogatták; ezért nincs olyan csúcs, amelyet be kellene illeszteni a sorba.
A következő csomópont a 6. Tehát a 6-ot töröljük a sorból. A rendszer kinyomtatja és látogatottként jelöli meg az alábbiak szerint:
linux parancs a zip-hez
Miután a 6. csomópont eltávolításra kerül a sorból, a 6. csomópont összes szomszédos csomópontja a meglátogatott csomópontok kivételével hozzáadódik a sorhoz. A 6. csomópont szomszédos csomópontjai 1 és 4. Mivel az 1. csomópontot már meglátogatták, és a 4. csomópont már hozzáadva van a Várólistához; ezért nincs beszúrandó csúcs a sorba.
A sor következő eleme a 4. Tehát a 4 törlődik a sorból. A rendszer kinyomtatja és látogatottként jelöli meg.
Miután a 4-es csomópont eltávolításra kerül a sorból, a 4-es csomópont összes szomszédos csomópontja a meglátogatott csomópontok kivételével hozzáadódik a sorhoz. A 4. csomópont szomszédos csomópontjai a 3, 2 és 6. Mivel az összes szomszédos csomópontot már meglátogatták; tehát nincs beszúrandó csúcs a sorba.
Mi az a DFS?
DFS a Depth First Search rövidítése. A DFS bejárásnál a verem adatszerkezetet használják, amely LIFO (Last In First Out) elven működik. A DFS-ben a bejárás bármely csomópontról elindítható, vagy azt is mondhatjuk, hogy bármelyik csomópont tekinthető gyökércsomópontnak mindaddig, amíg a gyökércsomópontot nem említik a problémában.
BFS esetén a sorból törölt elem, a törölt csomópont szomszédos csomópontjai hozzáadódnak a sorhoz. Ezzel szemben az elosztott fájlrendszerben a veremből eltávolított elemet a törölt csomópontnak csak egy szomszédos csomópontja adja hozzá a veremhez.
Tekintsük az alábbi grafikont a Mélység első keresésének bejárásához.
Tekintsük a 0-s csomópontot gyökércsomópontnak.
Először beillesztjük a 0 elemet a verembe az alábbiak szerint:
A 0-s csomópontnak két szomszédos csomópontja van, azaz az 1-es és a 3-as. Most már csak egy szomszédos csomópontot vehetünk át, az 1-et vagy a 3-at. Tegyük fel, hogy az 1. csomópontot tekintjük; ezért az 1 bekerül egy kötegbe, és az alábbiak szerint kerül kinyomtatásra:
térképek java
Most megnézzük az 1. csomópont szomszédos csúcsait. Az 1. csomópont nem látogatott szomszédos csúcsai a 3, 2, 5 és 6. E négy csúcs bármelyikét tekinthetjük. Tegyük fel, hogy vesszük a 3-as csomópontot, és beillesztjük a verembe az alábbiak szerint:
Tekintsük a 3. csomópont nem látogatott szomszédos csúcsait. A 3. csomópont nem látogatott szomszédos csúcsai 2 és 4. A csúcsok bármelyikét vehetjük, azaz a 2-t vagy a 4-et. Tegyük fel, hogy a 2-es csúcsot beillesztjük a verembe az alábbiak szerint:
A 2. csomópont nem látogatott szomszédos csúcsai 5 és 4. A csúcsok közül választhatunk, azaz 5 vagy 4. Tegyük fel, hogy a 4. csúcsot vesszük, és beszúrjuk a verembe az alábbiak szerint:
Most megvizsgáljuk a 4. csomópont nem látogatott szomszédos csúcsait. A 4. csomópont nem látogatott szomszédos csúcsa a 6. csomópont. Ezért a 6. elemet az alábbiak szerint helyezzük be a verembe:
Miután beszúrtuk a 6. elemet a verembe, megnézzük a 6. csomópont nem látogatott szomszédos csúcsait. Mivel a 6. csomópontnak nincsenek meglátogatott szomszédos csúcsai, így nem tudunk továbblépni a 6. csomóponton. Ebben az esetben végrehajtjuk visszalépés . A legfelső elem, azaz a 6 kiugrik a veremből az alábbiak szerint:
A verem legfelső eleme a 4. Mivel a 4-es csomópontból nem maradt meglátogatott szomszédos csúcs; ezért a 4. csomópont kikerül a veremből az alábbiak szerint:
A verem következő legfelső eleme a 2. Most a 2. csomópont nem látogatott szomszédos csúcsait nézzük. Mivel csak egy meg nem látogatott csomópont, azaz 5 maradt, így az 5. csomópont a 2 feletti verembe kerül, és kinyomtatásra kerül. az alábbiak szerint:
Most ellenőrizzük az 5. csomópont szomszédos csúcsait, amelyek még mindig nem látogattak. Mivel nem maradt meglátogatható csúcs, ezért az 5-ös elemet az alábbi módon emeljük ki a veremből:
Nem tudunk továbblépni 5-öt, ezért visszalépést kell végrehajtanunk. Visszalépéskor a legfelső elem kikerül a veremből. A legfelső elem az 5, amely kikerülne a veremből, és visszatérünk a 2. csomóponthoz az alábbiak szerint:
Most a 2. csomópont nem látogatott szomszédos csúcsait fogjuk ellenőrizni. Mivel nem maradt meglátogatandó szomszédos csúcs, ezért visszalépést végzünk. Visszalépéskor a legfelső elem, azaz a 2. kikerülne a veremből, és visszamegyünk a 3-as csomóponthoz az alábbiak szerint:
list.sort java
Most a 3. csomópont nem látogatott szomszédos csúcsait fogjuk ellenőrizni. Mivel nem maradt meglátogatandó szomszédos csúcs, ezért visszalépést végzünk. A visszalépéskor a legfelső elem, azaz a 3 kikerülne a veremből, és visszalépnénk az 1-es csomóponthoz az alábbiak szerint:
A 3. elem kiugrása után ellenőrizzük az 1. csomópont nem látogatott szomszédos csúcsait. Mivel nem maradt meglátogatandó csúcs; ezért a visszalépés végrehajtásra kerül. A visszalépéskor a legfelső elem, azaz az 1 kikerülne a veremből, és visszalépnénk a 0-s csomóponthoz az alábbiak szerint:
Ellenőrizzük a 0 csomópont szomszédos csúcsait, amelyek még mindig nem látogattak. Mivel nem maradt meglátogatható szomszédos csúcs, ezért visszalépést végzünk. Ebben csak egy elem, azaz a veremben maradt 0 kerül ki a veremből az alábbiak szerint:
Ahogy a fenti ábrán is megfigyelhetjük, hogy a verem üres. Tehát itt le kell állítani a DFS-bejárást, és a kinyomtatott elemek a DFS-bejárás eredménye.
A BFS és a DFS közötti különbségek
A BFS és a DFS közötti különbségek a következők:
| BFS | DFS | |
|---|---|---|
| Teljes alak | A BFS a Breadth First Search rövidítése. | A DFS a Depth First Search rövidítése. |
| Technika | Ez egy csúcs alapú technika a gráf legrövidebb útjának megtalálására. | Ez egy él alapú technika, mivel az él mentén lévő csúcsokat először a kezdőponttól a végcsomópontig fedezzük fel. |
| Meghatározás | A BFS egy bejárási technika, amelyben először az azonos szintű csomópontokat fedezzük fel, majd lépünk a következő szintre. | A DFS egy bejárási technika is, amelyben a bejárás a gyökércsomóponttól indul, és a csomópontokat a lehető legmesszebbre feltárja, amíg el nem érjük azt a csomópontot, amelynek nincsenek meglátogatott szomszédos csomópontjai. |
| Adatstruktúra | A soradat-struktúra a BFS-bejáráshoz használatos. | A verem adatszerkezet a BFS bejáráshoz használatos. |
| Visszalépés | A BFS nem használja a visszalépés fogalmát. | A DFS visszalépést használ az összes meg nem látogatott csomópont bejárására. |
| Élek száma | A BFS megtalálja a legrövidebb utat, amelynek minimális számú éle van a forrástól a célcsúcsig. | Az elosztott fájlrendszerben több élre van szükség ahhoz, hogy a forráscsúcstól a célcsúcsig haladjunk. |
| Optimalitás | A BFS bejárás optimális azokhoz a csúcsokhoz, amelyeket a forráscsúcshoz közelebb kell keresni. | Az elosztott fájlrendszer bejárása optimális azokhoz a gráfokhoz, amelyekben a megoldások távol vannak a forráscsúcstól. |
| Sebesség | A BFS lassabb, mint a DFS. | A DFS gyorsabb, mint a BFS. |
| Alkalmasság döntési fának | Nem alkalmas a döntési fára, mert először az összes szomszédos csomópont feltárását igényli. | Alkalmas a döntési fára. A döntés alapján minden utat feltár. Amikor megtalálják a célt, leállítja a bejárást. |
| Hatékony memória | Nem memóriahatékony, mivel több memóriát igényel, mint a DFS. | Memóriahatékony, mivel kevesebb memóriát igényel, mint a BFS. |