Viikon 10 aiheena on luentomateriaalin sivut 422–483. Viikon tavoitteena on oppia tuntemaan verkkoihin liittyvää sanastoa sekä algoritmit syvyyshaku ja leveyshaku.
Sivuilla 484–505 on myös kiinnostavaa lisätietoa, johon voi tutustua halutessaan. :)
Vaihtoehtoinen suomenkielinen lähde verkkoalgoritmien opiskeluun on KKKK, jonka lähestyy asiaa käytännön ohjelmoinnin kannalta.
Hyvä tapa toteuttaa verkko Javalla on
luoda taulukko, joka sisältää jokaiselle solmulle
luettelon siitä lähtevistä kaarista.
Luettelona voi toimia esim. ArrayList
tai HashSet riippuen käyttötilanteesta.
Verkon määrittely voisi näyttää seuraavalta:
ArrayList<Integer>[] verkko = new ArrayList[n+1];
for (int i = 1; i <= n; i++) {
verkko[i] = new ArrayList<Integer>();
}
Tässä muuttuja n sisältää solmujen määrän
ja solmut on numeroitu 1..n.
Huomaa, että ensimmäisen määrittelyn lopussa ei saa
lukea <Integer>,
tai Java ei suostu kääntämään koodia.
Syvyyshaku on yksinkertaisin tapa käydä läpi verkossa olevat solmut. Syvyyshaku lähtee liikkeelle jostakin solmusta ja vierailee kaikissa solmuissa, joihin kyseisestä solmusta pääsee.
Syvyyshaku on mukavinta toteuttaa rekursiivisesti, jolloin riittää lyhyt koodi. Luennolla käytiin läpi yksi tapa koodata syvyyshaku, ja voit katsoa sen tästä.
Leveyshaku on vaihtoehtoinen tapa käydä läpi verkon solmut. Se eroaa syvyyshausta siinä, että solmut käydään läpi siinä järjestyksessä, mikä on niiden etäisyys lähtösolmusta. Niinpä leveyshaun avulla voi selvittää, mikä on lyhin polku kaikkiin muihin solmuihin lähtösolmusta.
Leveyshaku on vaikeampi toteuttaa kuin syvyyshaku, mutta se on tarpeen silloin, jos tehtävänä on etsiä lyhimpiä polkuja.