BFS un DFS ir grafiku meklēšanā izmantotās metodes. Grafika pārvietošana ir process, kurā tiek apmeklēti visi grafika mezgli. Grafiks ir Vertices 'V' un Edges 'E' grupa, kas savieno virsotnes.
Salīdzinājuma diagramma
| Salīdzināšanas pamats | BFS | DFS |
|---|---|---|
| Pamata | Vertex-algoritms | Uz malām balstīts algoritms |
| Datu struktūra, ko izmanto, lai saglabātu mezglus | Rinda | Kaudze |
| Atmiņas patēriņš | Neefektīva | Efektīvs |
| Konstruktīvā koka struktūra | Plašs un īss | Šaura un gara |
| Pārbrauktuve | Vispirms tiek izpētītas vecākās neredzētas virsotnes. | Sākumā tiek pētītas vertikāli gar malu. |
| Optimitāte | Optimāls, lai atrastu īsāko attālumu, nevis izmaksas. | Nav optimāls |
| Pieteikums | Pārbauda divpusējo grafiku, savienoto komponentu un īsāko ceļu, kas atrodas grafikā. | Pārbauda divu malu savienoto grafiku, stingri saistītu grafiku, aciklisko grafiku un topoloģisko secību. |
BFS definīcija
Pirmais meklējums (BFS) ir grafikā izmantotā šķērsošanas metode. Tā izmanto rindu apmeklēto virsotņu glabāšanai. Šajā metodē uzsvars tiek likts uz grafika virsotnēm, vispirms tiek izvēlēts viens virsotne, tad to apmeklē un atzīmē. Virzieni, kas atrodas blakus apmeklētajam virsotnei, pēc tam tiek apmeklēti un saglabāti rindā. Līdzīgi saglabātie virsotnes tiek apstrādāti pa vienam, un viņu blakus esošie virsotnes tiek apmeklēti. Mezgls tiek pilnībā izpētīts pirms apmeklējuma jebkurā citā diagrammā, citiem vārdiem sakot, vispirms tas šķērso seklākos neizpētītos mezglus.
Piemērs
Mums ir grafiks, kura virsotnes ir A, B, C, D, E, F, G. Ņemot vērā A kā sākuma punktu. Procesa darbības ir šādas:
- A virsotne tiek paplašināta un saglabāta rindā.
- Vertikāli B, D un G A pēctecis tiek paplašināts un saglabāts rindā, bet tajā pašā laikā Vertex A tiek noņemts.
- Tagad B rindas priekšpusē tiek noņemta kopā ar tā pēctecīgo virsotņu E un F saglabāšanu.
- Vertex D atrodas rindas priekšpusē, un tā pieslēgtais mezgls F jau ir apmeklēts.
- Vertex G tiek noņemta no rindas, un tai ir pēctecis E, kas jau ir apmeklēts.
- Tagad E un F tiek noņemtas no rindas, un tā pēctecis C tiek šķērsots un saglabāts rindā.
- Pēdējā C ir arī noņemta un rinda ir tukša, kas nozīmē, ka mēs esam darījuši.
- Radītais izeja ir - A, B, D, G, E, F, C.
BFS var būt noderīgs, nosakot, vai grafikā ir pievienoti komponenti, vai ne. Un arī to var izmantot, lai atklātu divpusēju diagrammu .
Grafiks ir divpusējs, kad grafa virsotnes ir sadalītas divos disjektoros; tajā pašā komplektā nebūtu divu blakus esošo virsotņu. Vēl viena bipartīta diagrammas pārbaudes metode ir pārbaudīt nepāra cikla rašanos grafikā. Divpusējā diagramma nedrīkst saturēt nepāra ciklu.
BFS ir arī labāk atrast īsāko ceļu grafikā, ko varētu uzskatīt par tīklu.
DFS definīcija
Dziļuma pirmā meklēšana (DFS) metode izmanto apmeklēto virsotņu glabāšanai paredzēto kaudzīti. DFS ir uz malu balstīta metode un darbojas rekursīvā veidā, kur virsotnes tiek pētītas pa ceļu (malu). Mezgla izpēte tiek apturēta, tiklīdz tiek atrasts cits neizpētīts mezgls, un vissvarīgākie ir visdziļākie neizpētītie mezgli. DFS šķērso / apmeklē katru virsotni tieši vienu reizi, un katra mala tiek pārbaudīta tieši divas reizes.
Piemērs
Līdzīgi kā BFS ļauj veikt tādu pašu grafiku, lai veiktu DFS operācijas, un iesaistītās darbības ir šādas:
- Uzskatot A par sākumpunktu, kas tiek pētīts un glabāts kaudzē.
- B secīgā virsotne A tiek glabāta kaudzē.
- Vertex B ir divi E un F pēcteci, starp tiem alfabētiski E tiek pētīta un saglabāta kaudzē.
- Virzienā tiek saglabāts virsotnes E pēctecis, ti, G.
- Vertex G ir divas savienotas virsotnes, un abas jau ir apmeklētas, tāpēc G tiek izlaists no kaudzes.
- Līdzīgi, arī Es ir noņemts.
- Tagad virsotne B atrodas kaudzes augšdaļā, tā otrais mezgls (virsotne) F tiek pētīta un saglabāta kaudzē.
- Vertex F ir divi C un D pēcteci, starp tiem C vispirms šķērso un uzglabā kaudzē.
- Vertex C ir tikai viens priekštecis, kas jau ir apmeklējis, tāpēc tas tiek noņemts no kaudzes.
- Tagad galotne D, kas savienota ar F, tiek apmeklēta un saglabāta kaudzē.
- Tā kā virsotnei D nav nevienu neredzētu mezglu, D tiek noņemts.
- Līdzīgi tiek parādīti arī F, B un A.
- Radītais izeja ir A, B, E, G, F, C, D.
DFS lietojumprogrammas ietver divu malu savienotu grafiku, stipri savienotu grafiku, aciklisko grafiku un topoloģisko kārtību .
Grafiku sauc par divām malām, kas savienotas, ja tās ir savienotas, pat ja viena no malām ir noņemta. Šī lietojumprogramma ir ļoti noderīga datortīklos, kuros viena tīkla saikne neietekmēs atlikušo tīklu, un tas joprojām būtu savienots.
Stingri savienots grafiks ir grafiks, kurā jāatrodas ceļam starp pasūtīto virsotņu pāri. DFS tiek izmantots virzītajā grafikā, lai meklētu ceļu starp katru pasūtīto virsotņu pāri. DFS var viegli atrisināt savienojamības problēmas.
Galvenās atšķirības starp BFS un DFS
- BFS ir algoritms, kas balstās uz virsotni, bet DFS ir ar algoritmu.
- BFS izmanto rindas datu struktūru. No otras puses, DFS izmanto kaudzīti vai rekursiju.
- Atmiņas vieta tiek efektīvi izmantota DFS, bet telpas izmantošana BFS nav efektīva.
- BFS ir optimāls algoritms, bet DFS nav optimāls.
- DFS veido šaurus un garus kokus. Pretstatā BFS veido plašu un īsu koku.
Secinājums
BFS un DFS, abām grafiku meklēšanas metodēm ir līdzīgs darbības laiks, bet atšķirīgs telpas patēriņš, DFS ņem lineāru telpu, jo mums jāatceras viens ceļš ar neizpētītiem mezgliem, bet BFS saglabā katru mezglu atmiņā.
DFS dod dziļākus risinājumus un nav optimāls, bet tas darbojas labi, ja risinājums ir blīvs, bet BFS ir optimāls, kas vispirms meklē optimālo mērķi.
