Pirms aplūkot atšķirības starp BFS un DFS, mums vispirms būtu jāzina par BFS un DFS atsevišķi.

Kas ir BFS?

BFS apzīmē Platuma pirmā meklēšana . Tas ir pazīstams arī kā līmeņa pasūtījuma šķērsošana . Rindas datu struktūra tiek izmantota meklēšanas platumam vispirms. Ja grafā izmantojam BFS algoritmu, mēs varam uzskatīt jebkuru mezglu par saknes mezglu.

Apskatīsim tālāk redzamo diagrammu, kas parāda pirmās meklēšanas šķērsošanas platumu.

java pārvērst char par int

Pieņemsim, ka mēs uzskatām mezglu 0 par saknes mezglu. Tāpēc šķērsošana tiktu sākta no mezgla 0.

Kad mezgls 0 tiek noņemts no rindas, tas tiek izdrukāts un atzīmēts kā a apmeklētais mezgls.

Kad mezgls 0 tiek noņemts no rindas, blakus esošie mezgla 0 mezgli tiks ievietoti rindā, kā parādīts tālāk:

Tagad mezgls 1 tiks noņemts no rindas; tas tiek izdrukāts un atzīmēts kā apmeklēts mezgls

Kad 1. mezgls tiek noņemts no rindas, visi blakus esošie mezgla 1 mezgli tiks pievienoti rindai. 1. mezgla blakus esošie mezgli ir 0, 3, 2, 6 un 5. Taču rindā ir jāievieto tikai neapmeklēti mezgli. Tā kā mezgli 3, 2, 6 un 5 ir neapmeklēti; tāpēc šie mezgli tiks pievienoti rindā, kā parādīts tālāk:

Nākamais mezgls ir 3 rindā. Tātad 3. mezgls tiks noņemts no rindas, tas tiks izdrukāts un atzīmēts kā apmeklēts, kā parādīts zemāk:

Kad 3. mezgls tiek noņemts no rindas, visi blakus esošie 3. mezgla mezgli, izņemot apmeklētos mezglus, tiks pievienoti rindā. 3. mezgla blakus esošie mezgli ir 0, 1, 2 un 4. Tā kā mezgli 0, 1 jau ir apmeklēti un 2. mezgls atrodas rindā; tāpēc rindā jāievieto tikai 4. mezgls.

Aktrise Sai Pallavi

Tagad nākamais mezgls rindā ir 2. Tātad 2 tiks dzēsti no rindas. Tas tiek izdrukāts un atzīmēts kā apmeklēts, kā parādīts zemāk:

Kad 2. mezgls tiek noņemts no rindas, visi blakus esošie 2. mezgla mezgli, izņemot apmeklētos mezglus, tiks pievienoti rindā. 2. mezgla blakus mezgli ir 1, 3, 5, 6 un 4. Tā kā mezgli 1 un 3 jau ir apmeklēti, un 4, 5, 6 jau ir pievienoti rindā; tādēļ mums nav jāievieto neviens mezgls rindā.

Nākamais elements ir 5. Tātad 5 tiks dzēsti no rindas. Tas tiek izdrukāts un atzīmēts kā apmeklēts, kā parādīts zemāk:

Kad 5. mezgls tiek noņemts no rindas, visi blakus esošie 5. mezgla mezgli, izņemot apmeklētos mezglus, tiks pievienoti rindā. 5. mezgla blakus mezgli ir 1 un 2. Tā kā abi mezgli jau ir apmeklēti; tāpēc rindā nav jāievieto neviena virsotne.

Nākamais mezgls ir 6. Tātad 6 tiks dzēsti no rindas. Tas tiek izdrukāts un atzīmēts kā apmeklēts, kā parādīts zemāk:

Kad mezgls 6 tiek noņemts no rindas, visi blakus esošie mezgla 6 mezgli, izņemot apmeklētos mezglus, tiks pievienoti rindā. 6. mezgla blakus mezgli ir 1 un 4. Tā kā 1. mezgls jau ir apmeklēts un 4. mezgls jau ir pievienots rindā; tāpēc rindā nav jāievieto virsotne.

savienojiet datubāzi java

Nākamais rindas elements ir 4. Tātad 4 tiks dzēsti no rindas. Tas tiek izdrukāts un atzīmēts kā apmeklēts.

Kad 4. mezgls tiks noņemts no rindas, visi blakus esošie 4. mezgla mezgli, izņemot apmeklētos mezglus, tiks pievienoti rindā. 4. mezgla blakus mezgli ir 3, 2 un 6. Tā kā visi blakus esošie mezgli jau ir apmeklēti; tātad, rindā nav jāievieto neviena virsotne.

Kas ir DFS?

DFS apzīmē Depth First Search. DFS šķērsošanā tiek izmantota steka datu struktūra, kas darbojas pēc LIFO (Last In First Out) principa. DFS sistēmā šķērsošanu var sākt no jebkura mezgla vai arī mēs varam teikt, ka jebkuru mezglu var uzskatīt par saknes mezglu, kamēr saknes mezgls nav minēts problēmā.

BFS gadījumā rindai tiek pievienots elements, kas tiek izdzēsts no rindas, blakus esošie dzēstā mezgla mezgli. Turpretim DFS, elements, kas tiek noņemts no steka, stekam tiek pievienots tikai viens blakus esošais dzēstā mezgla mezgls.

Apskatīsim tālāk redzamo diagrammu, lai parādītu pirmās dziļuma meklēšanas šķērsošanu.

Apsveriet mezglu 0 par saknes mezglu.

Pirmkārt, mēs ievietojam elementu 0 kaudzē, kā parādīts zemāk:

Mezglam 0 ir divi blakus mezgli, t.i., 1 un 3. Tagad šķērsošanai varam ņemt tikai vienu blakus esošo mezglu, vai nu 1, vai 3. Pieņemsim, ka mēs uzskatām mezglu 1; tādēļ 1 tiek ievietots kaudzē un tiek izdrukāts, kā parādīts tālāk:

Tagad apskatīsim 1. mezgla blakus virsotnes. Neapmeklētās mezgla 1 blakus virsotnes ir 3, 2, 5 un 6. Mēs varam uzskatīt jebkuru no šīm četrām virsotnēm. Pieņemsim, ka mēs ņemam mezglu 3 un ievietojam to kaudzē, kā parādīts zemāk:

Apsveriet 3. mezgla neapmeklētās blakus virsotnes. 3. mezgla neapmeklētās blakus virsotnes ir 2 un 4. Mēs varam ņemt jebkuru no virsotnēm, t.i., 2 vai 4. Pieņemsim, ka mēs ņemam virsotni 2 un ievietojam to kaudzē, kā parādīts zemāk:

Linux kā pārdēvēt direktoriju

Neapmeklētās 2. mezgla blakus virsotnes ir 5 un 4. Mēs varam izvēlēties vienu no virsotnēm, t.i., 5 vai 4. Pieņemsim, ka mēs ņemam virsotni 4 un ievietojam kaudzē, kā parādīts zemāk:

Tagad mēs apskatīsim 4. mezgla neapmeklētās blakus virsotnes. 4. mezgla neapmeklētā blakus virsotne ir 6. mezgls. Tāpēc elements 6 tiek ievietots kaudzē, kā parādīts zemāk:

Pēc elementa 6 ievietošanas kaudzē apskatīsim 6. mezgla neapmeklētās blakus virsotnes. Tā kā mezglam 6 nav neapmeklētu blakus virsotņu, mēs nevaram pārvietoties tālāk par 6. mezglu. Šajā gadījumā mēs veiksim atkāpšanās . Augšējais elements, t.i., 6, tiks izvilkts no kaudzes, kā parādīts tālāk:

Augšējais elements kaudzītē ir 4. Tā kā no 4. mezgla nav palicis nevienas neapmeklētas blakus virsotnes; tāpēc 4. mezgls tiek izmests no kaudzes, kā parādīts zemāk:

Nākamais augšējais elements kaudzē ir 2. Tagad mēs apskatīsim 2. mezgla neapmeklētās blakus virsotnes. Tā kā ir palicis tikai viens neapmeklēts mezgls, t.i., 5, tad mezgls 5 tiks iebīdīts kaudzē virs 2 un tiek izdrukāts. kā parādīts zemāk:

Tagad mēs pārbaudīsim blakus esošās 5. mezgla virsotnes, kas joprojām ir neapmeklētas. Tā kā vairs nav nevienas virsotnes, ko apmeklēt, mēs izņemam elementu 5 no kaudzes, kā parādīts zemāk:

Mēs nevaram pārvietoties tālāk par 5, tāpēc mums ir jāveic atkāpšanās. Atkāpjoties, augšējais elements tiktu izmests no steka. Augšējais elements ir 5, kas tiktu izmests no kaudzes, un mēs pārejam atpakaļ uz mezglu 2, kā parādīts tālāk:

Tagad mēs pārbaudīsim 2. mezgla neapmeklētās blakus virsotnes. Tā kā nav palikušas nevienas blakus esošās virsotnes, ko apmeklēt, mēs veicam atpakaļsekošanu. Atkāpjoties, augšējais elements, t.i., 2, tiktu izcelts no kaudzes, un mēs pārietam atpakaļ uz mezglu 3, kā parādīts tālāk:

Tagad mēs pārbaudīsim 3. mezgla neapmeklētās blakus virsotnes. Tā kā nav palikušas nevienas blakus esošās virsotnes, ko apmeklēt, mēs veicam atkāpšanos. Atkāpjoties, augšējais elements, t.i., 3, tiktu izcelts no steka, un mēs pārietam atpakaļ uz mezglu 1, kā parādīts tālāk:

javascript daudzrindu virkne

Pēc 3. elementa izvēršanas mēs pārbaudīsim neapmeklētās 1. mezgla blakus virsotnes. Tā kā nav palikušas nevienas virsotnes, ko apmeklēt; tāpēc tiks veikta atkāpšanās. Atkāpjoties, augšējais elements, t.i., 1, tiktu izcelts no steka, un mēs pārietam atpakaļ uz mezglu 0, kā parādīts tālāk:

Mēs pārbaudīsim blakus esošās mezgla 0 virsotnes, kas joprojām ir neapmeklētas. Tā kā nav palikusi neviena blakus virsotne, ko apmeklēt, tāpēc mēs veicam atkāpšanos. Šajā gadījumā tikai viens elements, t.i., 0, kas palicis kaudzē, tiktu izmests no steka, kā parādīts tālāk:

Kā redzam attēlā, kaudze ir tukša. Tātad, mums šeit ir jāpārtrauc DFS šķērsošana, un izdrukātie elementi ir DFS šķērsošanas rezultāts.

Atšķirības starp BFS un DFS

Tālāk ir norādītas atšķirības starp BFS un DFS: