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: