BFS ja DFS ovat käyrämenetelmiä, joita käytetään kaavion etsinnässä. Kaavion kulku on prosessi, jossa käydään läpi kaikki kaavion solmut. Kaavio on Vertices 'V' ja Edges 'E', jotka yhdistyvät huippuihin.
Vertailukaavio
| Vertailun perusteet | BFS | DFS |
|---|---|---|
| perustiedot | Vertex-pohjainen algoritmi | Reunapohjainen algoritmi |
| Solmujen tallentamiseen käytetty tietorakenne | Jonottaa | Pino |
| Muistin kulutus | tehoton | Tehokas |
| Rakennetun puun rakenne | Leveä ja lyhyt | Kapea ja pitkä |
| Liikkuva muoti | Vanhimmat näkymätön huippupisteet tutkitaan aluksi. | Alussa tutkitaan reunoja pitkin olevia pisteitä. |
| optimality | Optimaalinen lyhyimmän matkan löytämiseksi, ei kustannuksella. | Ei optimaalinen |
| hakemus | Tutkii bipartite-käyrää, liitettyä komponenttia ja kaaviossa olevaa lyhintä reittiä. | Tutkii kahden reunan liitettyä kuvaajan, vahvasti kytkettyä kuvaajan, asyklisen kaavion ja topologisen järjestyksen. |
Määritelmä BFS
BFS (Bread) First Search (BFS) on kaavioissa käytettävä siirtomenetelmä. Se käyttää jonoa vierailevien pisteiden tallentamiseen. Tässä menetelmässä korostus on kaavion pisteissä, yksi kärki valitaan aluksi, sitten se vierailee ja merkitään. Vierailevan kärjen vieressä olevat pisteet käydään sitten ja tallennetaan jonoon peräkkäin. Samoin tallennetut pisteet käsitellään sitten yksi kerrallaan, ja niiden vierekkäiset pisteet käyvät. Solmu tutkitaan täysin ennen kuin vierailet millä tahansa muulla solmulla kaaviossa, toisin sanoen, se kulkee ensin matalimpien tutkimattomien solmujen läpi.
esimerkki
Meillä on kuvaaja, jonka pisteet ovat A, B, C, D, E, F, G. A-lähtökohtana. Prosessin vaiheet ovat seuraavat:
- Vertex A laajennetaan ja tallennetaan jonoon.
- A: n peräkkäiset B-, D- ja G-pisteet laajennetaan ja tallennetaan jonoon samalla, kun Vertex A poistetaan.
- Nyt jonon etupäässä oleva B poistetaan yhdessä sen seuraajapisteiden E ja F tallentamisen kanssa.
- Vertex D on jonon etupäässä ja sen liitetty solmu F on jo käynyt.
- Vertex G poistetaan jonosta, ja sillä on seuraaja E, joka on jo käynyt.
- Nyt E ja F poistetaan jonosta, ja sen seuraajan kärki C kulkee ja tallennetaan jonoon.
- Viimeisenä C on myös poistettu ja jono on tyhjä, mikä tarkoittaa, että olemme valmiit.
- Muodostettu lähtö on A, B, D, G, E, F, C.
BFS voi olla hyödyllinen, kun selvitetään, onko kuviossa liitetty komponentteja vai ei. Ja sitä voidaan käyttää myös kaksisuuntaisen kaavion tunnistamiseen.
Kaavio on kaksisuuntainen, kun kaavion pisteet on jaettu kahteen disjointiryhmään; samassa sarjassa ei sijaitse kaksi vierekkäistä huippua. Toinen menetelmä kaksisuuntaisen käyrän tarkistamiseksi on tarkistaa parittoman jakson esiintyminen kuviossa. Kaksisuuntainen kaavio ei saa sisältää paritonta sykliä.
BFS on myös parempi löytää lyhyin polku kaaviossa voitaisiin nähdä verkostona.
Määritelmä DFS
Syvyys Ensimmäinen haku (DFS) -liikutustapa käyttää pinoa vierailevien pisteiden tallentamiseen. DFS on reunapohjainen menetelmä ja se toimii rekursiivisella tavalla, jossa pisteet tutkitaan polulla (reuna). Solmun etsintä keskeytetään heti, kun löydetään toinen tutkimatta jäänyt solmu ja etsimään syvimmät tutkimattomat solmut. DFS kulkee / kulkee jokaisella kärjellä täsmälleen kerran ja kukin reuna tarkastetaan tarkasti kahdesti.
esimerkki
BFS: n kaltaisella tavalla voidaan tehdä sama kaavio DFS-operaatioiden suorittamiseksi, ja siihen liittyvät vaiheet ovat seuraavat:
- Ottaen huomioon A: n aloitusverkkona, jota tutkitaan ja tallennetaan pinoon.
- B-peräkkäinen huippupiste A tallennetaan pinoon.
- Vertex B: llä on kaksi seuraajaa E ja F, joista aakkosjärjestyksessä E tutkitaan ensin ja tallennetaan pinoon.
- Vertex E: n seuraaja, eli G, tallennetaan pinoon.
- Vertex G: llä on kaksi liitettyä pistettä, ja molemmat ovat jo vieraillut, joten G on poistettu pinosta.
- Samoin E on myös poistettu.
- Nyt piste B on pinon yläosassa, sen toinen solmu (kärki) F tutkitaan ja tallennetaan pinoon.
- Vertex F: llä on kaksi seuraajaa C ja D, joiden välillä C liikkuu ensin ja tallennetaan pinoon.
- Vertex C: ssä on vain yksi edeltäjä, joka on jo käynyt, joten se poistetaan pinosta.
- Nyt F: hen liitetty huippu D käydään ja tallennetaan pinoon.
- Koska vertex D: llä ei ole paljastamattomia solmuja, D poistetaan.
- Samoin F, B ja A ovat myös ponnahtaneet.
- Muodostettu lähtö on - A, B, E, G, F, C, D.
DFS: n sovelluksiin kuuluu kahden reunakytkennän piirroksen, voimakkaasti yhdistetyn käyrän, asyklisen graafin ja topologisen järjestyksen tarkastus .
Kaaviota kutsutaan kahdeksi reunaksi, jotka on kytketty, jos ja vain, jos se pysyy kytkettynä, vaikka yksi sen reunoista on poistettu. Tämä sovellus on erittäin hyödyllinen tietokoneverkoissa, joissa verkon yhden linkin vika ei vaikuta jäljellä olevaan verkkoon, ja se olisi edelleen yhteydessä.
Vahvasti yhdistetty kuvaaja on kaavio, jossa on oltava polku tilattujen parien välillä. DFS: ää käytetään suunnattuun kaavioon etsimään polkua jokaisen tilattujen parien välillä. DFS voi helposti ratkaista yhteysongelmia.
Tärkeimmät erot BFS: n ja DFS: n välillä
- BFS on huippupohjainen algoritmi, kun taas DFS on reunapohjainen algoritmi.
- BFS: ssä käytetään jonotietorakennetta. Toisaalta DFS käyttää pinota tai rekursiota.
- Muistitilaa hyödynnetään tehokkaasti DFS: ssä, kun taas tilan käyttö BFS: ssä ei ole tehokasta.
- BFS on optimaalinen algoritmi, kun taas DFS ei ole optimaalinen.
- DFS rakentaa kapeita ja pitkiä puita. Vastoin BFS rakentaa leveä ja lyhyt puu.
johtopäätös
BFS: llä ja DFS: llä, molemmilla kaavionhakutekniikoilla on samanlainen käyttöaika, mutta erilainen tilan kulutus, DFS vie lineaarista tilaa, koska meidän on muistettava yksi polku, jossa ei ole tutkittuja solmuja, kun taas BFS pitää kaikki solmut muistissa.
DFS tuottaa syvempiä ratkaisuja eikä ole optimaalinen, mutta se toimii hyvin, kun ratkaisu on tiheä, kun taas BFS on optimaalinen, joka etsii optimaalista tavoitetta aluksi.
