Kuvaajan liikkuminen
Kuvaajan läpikäynti tarkoittaa kaikkien pisteiden ja reunojen vierailua tarkalleen kerran kaivossa määritelty järjestys. Tiettyjen kaavioalgoritmien käytön aikana sinun on varmistettava, että kaavion jokaisessa kärjessä käydään tarkalleen kerran. Pisteiden vierailujärjestys on tärkeä ja se voi riippua ratkaisemistasi algoritmeista tai kysymyksistä.
Läpikäynnin aikana on tärkeää, että seuraat mitä pisteitä on käynyt. Yleisin tapa seurata huippuja on merkitä ne.
Leveyshaku (BFS)
Kuvaajia voi liikkua monella tapaa. BFS on yleisimmin käytetty lähestymistapa.
BFS on liikkuva algoritmi, jossa sinun tulisi aloittaa kulkeminen valitusta solmusta (lähde tai alkusolmu) ja kulkea kaavio kerroksittain tutkien näin naapurisolmuja (solmut, jotka on kytketty suoraan lähdesolmuun). Sinun on sitten siirryttävä kohti seuraavan tason naapurisolmuja.
Kuten nimi BFS ehdottaa, sinun on kuljettava kaavio leveästi seuraavasti:
- Siirrä ensin vaakasuoraan ja käy kaikissa nykyisen kerroksen solmuissa
- Siirry seuraavaan tasoon
Harkitse seuraavaa kaaviota. 
Kerroksen 1 solmujen välinen etäisyys on verrattain pienempi kuin kerroksen 2 solmujen välinen etäisyys. Siksi BFS: ssä sinun on kuljettava kaikki kerroksen 1 solmut ennen kuin siirryt kerroksen 2 solmuihin.
Alisolmujen kulkeminen
Kaavio voi sisältää jaksoja, jotka saattavat viedä sinut taas samaan solmuun kaavion liikkuessa. Voit välttää saman solmun käsittelyn uudelleen käyttämällä loogista taulukkoa, joka merkitsee solmun sen käsittelyn jälkeen. Kun vierailet solmuissa kaavion kerroksessa, tallenna ne tavalla, jolla voit kulkea vastaavat lapsisolmut samassa järjestyksessä.
Tämän prosessin helpottamiseksi tallenna solmu jonoon ja merkitse se ”käydyksi”, kunnes kaikki sen naapurit (siihen suoraan liitetyt pisteet) on merkitty. Jono noudattaa First In First Out (FIFO) -jonointimenetelmää, ja siksi solmun naapureita käydään siinä järjestyksessä kuin ne on lisätty solmuun, ts. Ensin lisättyyn solmuun käydään ensin. päällä.
Pseudokoodi
Liikkumisprosessi 
Liikkuva alkaa lähdesolmusta ja työntää s jonoon. s merkitään ”vierailtu”.
Ensimmäinen iterointi
- s ponnahtaa jonosta
- S: n eli 1 ja 2 naapurit kulkevat läpi
- 1 ja 2, joita ei ole aiemmin kulkettu, kulkevat. Ne ovat:
- työnnetty jonoon
- 1 ja 2 merkitään vieraille
Toinen iterointi
- 1 ponnahtaa jonosta
- 1 eli s ja 3 naapurit kulkevat läpi
- s jätetään huomiotta, koska se on merkitty ”käydyksi”
- 3, jota ei ole aiemmin kulkettu, kulkee. Se on:
- työnnetty jonoon
- merkitty vierailuksi
kolmas iteraatio
- 2 ponnahtaa jonosta
- 2 naapurin eli s, 3 ja 4 naapurit kulkevat läpi
- 3 ja s jätetään huomiotta, koska ne on merkitty vierailulle
- 4, jota ei ole aiemmin kulkettu, kulkee. Se on:
- työnnetty jonoon
- merkitty käydyksi
neljäs iterointi
- 3 ponnahtaa jonosta
- Kolmen eli 1, 2 ja 5 naapurit kulkevat läpi
- 1 ja 2 jätetään huomiotta, koska ne on merkitty ”vieraille”
- 5, jota ei ole aiemmin kulkettu, kulkee. Se on:
- työnnetty jonoon
- merkitty käydyksi
viides iterointi
- 4 ponnahtaa jonosta
- 4: n eli 2: n naapurit kulkevat läpi
- 2 jätetään huomioimatta, koska se on jo merkitty ”vierailuksi”
Kuudes iterointi
- 5 ponnahtaa jonosta
- 5 eli 3 naapurit kulkevat läpi
- 3 jätetään huomiotta, koska se on jo merkitty ”vierailuksi”
Jono on tyhjä ja se tulee ulos silmukasta. Kaikki solmut on ylitetty käyttämällä BFS: ää.
Jos kaavion kaikki reunat ovat saman painoisia, niin BFS: ää voidaan käyttää myös etsimään kaavion solmujen välinen vähimmäisetäisyys.
Esimerkki
Kuten tässä kaaviossa, aloita lähdesolmusta löytääksesi lähteen välinen etäisyys solmu ja solmu 1. Jos et noudata BFS-algoritmia, voit siirtyä lähdesolmusta solmuun 2 ja sitten solmuun 1. Tämä lähestymistapa laskee lähdesolmun ja solmun 1 välisen etäisyyden 2: ksi, kun taas etäisyys on itse asiassa 1. Pienin etäisyys voidaan laskea oikein käyttämällä BFS-algoritmia.
Monimutkaisuus
BFS: n aikakompleksi on O (V + E), missä V on solmujen ja E reunojen lukumäärä.
Sovellukset
1. Kuinka määritetään kunkin solmun taso annetussa puussa?
Kuten tiedät BFS: ssä, kuljet tasolta viisaasti. BFS: n avulla voit myös määrittää kunkin solmun tason.
Toteutus
Tämä koodi on samanlainen kuin BFS-koodi, ja siinä on vain seuraava ero:
taso] = taso + 1;
Tässä koodissa, kun vierailet jokaisessa solmussa, kyseisen solmun taso asetetaan lisäämällä sen yläsolmun tasoa. Näin määritetään kunkin solmun taso.
2 . 0-1 BFS
Tämän tyyppistä BFS: ää käytetään etsimään kaavion kahden solmun välinen lyhin etäisyys edellyttäen, että kaavion reunojen paino on 0 tai 1. Jos käytät aiemmin selitettyä BFS: ää, Tässä artikkelissa saat virheellisen tuloksen kahden solmun optimaaliselle etäisyydelle.
Tässä lähestymistavassa loogista taulukkoa ei käytetä solmun merkitsemiseen, koska optimaalisen etäisyyden kunto tarkistetaan, kun käy jokaisessa solmussa. Solmun tallentamiseen käytetään kaksipäistä jonoa. Jos 0-1 BFS: ssä reunan paino = 0, solmu työnnetään purkamisen eteen. Jos reunan paino = 1, solmu työnnetään purun takaosaan.
Toteutus
Q on kaksipäinen jono. Etäisyys on matriisi, jossa etäisyys sisältää etäisyyden aloitussolmusta v-solmuun. Aluksi lähdesolmusta määritetty etäisyys kuhunkin solmuun on ääretön.
Ymmärretään tämä koodi seuraavan kaavion avulla:
Kaavion vierekkäisyysluettelo on seuraava:
Tässä ”s”: tä pidetään 0: na tai lähdesolmuna.
0 – > 1 – > 3 – > 2
reunat. ensimmäinen = 1, reunat. toinen = 1
reunat. ensimmäinen = 3, reunat. toinen = 0
reunat. ensimmäinen = 2, reunat. toinen = 1
1 – > 0 – > 4
reunaa. ensimmäinen = 0, reunaa. sekunti = 1
reunaa. ensimmäinen = 4 , reunat.sekunnin = 0
2 – > 0 – > 3
reunat.first = 0 , reunat.second = 0
reunat.first = 3, reunat.second = 0
3 – > 0 – > 2 – > 4
reunat. ensimmäinen = 0, reunat. sekunti = 0
reunat. ensimmäinen = 2, reunat. toinen = 0
reunat.ensimmäinen = 4, reunat.sekunnin = 0
4 – > 1 – > 3
reunat.ensimmäinen = 1, reunat.sekunnin = 0
reunat.first = 3, reunat.sekunnin = 0
Jos käytät BFS-algoritmia, tulos on virheellinen, koska se näyttää sinulle optimaalinen etäisyys s: n välillä ja solmu 1 ja s ja solmu 2 vastaavasti. Tämä johtuu siitä, että se vierailee s: n lapsissa ja laskee s: n ja lastensa välisen etäisyyden, joka on 1. Todellinen optimaalinen etäisyys on 0 molemmissa tapauksissa.
Käsitellään
Lähtösolmusta eli 0: sta alkaen se siirtyy kohti 1, 2 ja 3. Koska reunan paino 0: n ja 1: n välillä 0 ja 2 on 1, vastaavasti , 1 ja 2 työnnetään jonon takaosaan. Koska reunan paino välillä 0 ja 3 on 0, 3 työnnetään jonon eteen. Etäisyys säilytetään etäisyysryhmässä vastaavasti.
3 ponnahtaa sitten jonosta ja samaa prosessia sovelletaan sen naapureihin ja niin edelleen.