BFS ir DFS - tai skersiniai metodai, naudojami ieškant grafiko. Grafiko judėjimas - tai procesas, kuriame lankomi visi grafiko mazgai. Grafikas yra vertikalių „V“ ir „E“ briaunų, jungiančių prie viršūnių, grupė.
Palyginimo diagrama
| Palyginimo pagrindas | BFS | DFS |
|---|---|---|
| Pagrindinis | Vertex-algoritmas | Briauna pagrįstas algoritmas |
| Duomenų struktūra, naudojama mazgų saugojimui | Eilė | Stack |
| Atminties naudojimas | Neefektyvus | Efektyvus |
| Pastatyto medžio struktūra | Platus ir trumpas | Siauras ir ilgas |
| Keliauti | Iš pradžių tiriamos seniausios nepraneštos viršūnės. | Pradžioje tiriamos vertikalės palei kraštą. |
| Optimumas | Optimalus rasti trumpiausią atstumą, o ne kaina. | Neoptimalus |
| Taikymas | Nagrinėja dvipusis grafikas, prijungtas komponentas ir trumpiausias kelias, esantis diagramoje. | Išnagrinėja dviejų kraštų sujungtą grafiką, stipriai sujungtą grafiką, aciklinį grafiką ir topologinę tvarką. |
BFS apibrėžimas
Breads First Search (BFS) yra grafikuose naudojamas judėjimo metodas. Jis naudoja eilę lankomų viršūnių saugojimui. Šiame metode pabrėžimas yra grafiko viršūnėse, iš pradžių pasirenkamas vienas viršūnė, tada jis aplankomas ir pažymimas. Po to lankomos viršūnės gretimos viršūnės yra paleidžiamos ir saugomos eilėje. Panašiai saugomi viršūnės apdorojami po vieną, o jų gretimos viršūnės aplankomos. Prieš apsilankant bet kuriame grafike esančiame mazge, visas mazgas yra visiškai ištirtas, kitaip tariant, pirmiausia jis pereina sekliausius neištirtus mazgus.
Pavyzdys
Turime grafiką, kurio viršūnės yra A, B, C, D, E, F, G. Atsižvelgiant į A pradžios tašką. Proceso veiksmai yra šie:
- A viršūnė yra išplėsta ir saugoma eilėje.
- A, B ir D pakopos, A, yra plečiamos ir saugomos eilėje.
- Dabar B eilės priekiniame gale pašalinama kartu su jų sekančių viršūnių E ir F saugojimu.
- Vertex D yra iš eilės priekio, o jo prijungtas mazgas F jau yra aplankytas.
- „Vertex G“ pašalinama iš eilės ir ji turi E įpėdinį, kuris jau yra aplankytas.
- Dabar E ir F yra pašalinami iš eilės, o jo įpėdinis C yra perkeliamas ir saugomas eilėje.
- Paskutiniame C taip pat pašalinamas ir eilė yra tuščia, o tai reiškia, kad mes darome.
- Sukurta išvestis yra - A, B, D, G, E, F, C.
BFS gali būti naudinga nustatant, ar grafikas turi prijungtų komponentų, ar ne. Be to, jis gali būti naudojamas dvimatės diagramos aptikimui.
Grafikas yra dvipusis, kai grafų viršūnės suskirstytos į du atskirus rinkinius; viename rinkinyje nebūtų dviejų gretimų viršūnių. Kitas dvipusio grafiko tikrinimo būdas yra tikrinti nelyginio ciklo atsiradimą grafike. Dvipusis grafikas neturi apimti nelyginio ciklo.
BFS taip pat geriau rasti trumpiausią maršrutą grafike, kuris gali būti vertinamas kaip tinklas.
DFS apibrėžimas
Pirmos paieškos (DFS) judėjimo metodas naudoja aplanką, kuriame saugomos aplankytos viršūnės. DFS yra krašto metodas ir veikia rekursyviai, kai viršūnės yra ištirtos keliu (kraštu). Mazgo tyrimas sustabdomas, kai tik randamas kitas neištirtas mazgas, o svarbiausi neišnagrinėti mazgai. DFS perkelia / aplanko kiekvieną viršūnę tiksliai vieną kartą ir kiekvienas kraštas tikrinamas tiksliai du kartus.
Pavyzdys
Panašiai kaip ir BFS, atlikite tą pačią diagramą atliekant DFS operacijas, ir susiję veiksmai yra:
- Laikant A kaip pradinį viršūnę, kuri yra ištirta ir saugoma kamino.
- B sekos viršūnė A yra saugoma kamino.
- Vertex B turi du E ir F įpėdinius, tarp jų ir pagal abėcėlę E pirmiausia tiriama ir saugoma kamino.
- Viršutinė E viršūnė, ty G yra saugoma kamino.
- „Vertex G“ turi dvi prijungtas viršūnes, ir abi jau yra aplankytos, todėl „G“ išstumiama iš kamino.
- Panašiai E taip pat pašalintas.
- Dabar viršūnė B yra kamino viršuje, jo kitas mazgas (viršūnė) F tiriamas ir saugomas kamino.
- Vertex F turi du įpėdinius C ir D, tarp jų C pirmiausia perkeliama ir saugoma kamino.
- Vertex C turi tik vieną pirmtaką, kuris jau yra aplankytas, todėl jis pašalinamas iš kamino.
- Dabar „F“ prijungtas viršūnė D yra laikoma ir saugoma kamino.
- Kadangi viršūnė D neturi jokių nepageidaujamų mazgų, todėl D yra pašalintas.
- Panašiai taip pat pasirodo F, B ir A.
- Gautas išėjimas yra - A, B, E, G, F, C, D.
DFS taikymas apima dviejų briaunų sujungtų grafikų, stiprių jungčių grafiko, aciklinio grafiko ir topologinės tvarkos patikrinimą .
Grafikas vadinamas dviem kraštais, prijungtais, jei ir tik tada, jei jis lieka prijungtas, net jei vienas iš jo kraštų yra pašalintas. Ši programa yra labai naudinga kompiuterių tinkluose, kuriuose vieno tinklo ryšio gedimas neturės įtakos likusiam tinklui, ir jis vis tiek būtų prijungtas.
Stipriai sujungtas grafikas yra grafikas, kuriame turi būti kelias tarp užsakytų viršūnių poros. DFS naudojamas nukreiptame grafike ieškant kelio tarp kiekvienos užsakytos viršūnių poros. DFS gali lengvai išspręsti ryšio problemas.
Pagrindiniai BFS ir DFS skirtumai
- BFS yra pagal tipą pagrįstas algoritmas, o DFS yra krašto pagrindu sukurtas algoritmas.
- BFS naudoja eilės duomenų struktūrą. Kita vertus, DFS naudoja steką arba rekursiją.
- Atminties erdvė efektyviai naudojama DFS, o erdvės panaudojimas BFS nėra veiksmingas.
- BFS yra optimalus algoritmas, o DFS nėra optimalus.
- DFS konstruoja siaurus ir ilgus medžius. BFS konstruoja platų ir trumpą medį.
Išvada
BFS ir DFS, abu grafų paieškos metodai turi panašų veikimo laiką, tačiau skirtingas erdvės suvartojimas, DFS užima linijinę erdvę, nes turime prisiminti vieną kelią su neištirtais mazgais, o BFS saugo kiekvieną atmintį.
DFS duoda gilesnių sprendimų ir nėra optimalus, tačiau jis veikia gerai, kai tirpalas yra tankus, o BFS yra optimalus, kuris iš pradžių ieško optimalaus tikslo.
