Graafid Graaf koosneb punktidest ehk sõlmedest ning nende omavahelistest ühendustest servadest ehk kaartest. Graafina saab esitada näiteks linnu ning neid ühendavaid teid. Veebilehti ja nende omavahelisi viiteid. Inimesi ning nende vahelisi tutvusi. Üheks võimaluseks graafid arvutile mõistetavaks teha on teatada sõlmede arv ning seotud sõlmede paarid ükshaaval. Mõnikord esitatakse andmed ka tabelina, kus nii ridade kui veergude arv on võrdne sõlmede arvuga. Ning kui kaks sõlme on omavahel seotud, siis on vastava numbriga rea ja veeru ristumiskohal seda tähistav väärtus. Näiteks arv 1. Esimesestes näidetes eeldame, et seotus on mõlemapoolne. St., et kui inimene nr. 3 tunneb inimest nr. 5, siis tunneb viies inimene ka kolmandat inimest. Ehk mõlemal juhul, kus kohtuvad viies rida ja kolmas veerg või viies veerg ja kolmas rida on kirjas 1. Üksteist mitte tundvate inimeste ridade ja veergude ristumiskohtades on arv 0. Ülesandeid * Koosta kahemõõtmeline (nt. 10x10) täisarvude massiiv. Täida nullidega. * Loo alamprogramm serva märkimiseks graafis. Parameetrina antakse ette ühendatavate sõlmede järjekorranumbrid. Nii vastava rea ja veeru kui veeru ja rea ristumiskohale kirjutatakse 1. Korduv serva märkimine olukorda ei muuda. * Loo alamprogramm massiivi trükkimiseks ekraanile. * Loo alamprogramm massiivi trükkimiseks faili. Esimesel real on sõlmede arv, edasi tuleb tabel nullide ja ühtedega näitamaks sõlmede omavahelisi seoseid. * Loo alamprogramm eelpool loodud massiivi andmete lugemiseks failist. * Faili esimesel real on kirjas sõlmede arv. Edasi on igal real kirjas kaks arvu, näitamaks, millised sõlmed on omavahel kaarega seotud. Loe nende andmete põhjal tulemus mällu kahemõõtmelisse massiivi. Trüki massiiv. * Koosta alamprogramm serva tekitamiseks kahe juhuslikult valitud sõlme vahel. Sõlmepaare valitakse senikaua, kuni leitakse paar, mille vahel veel polnud serva. * Koosta alamprogramm, mis loob etteantud mõõtmetega ning soovitud arvu juhuslike servadega graafi. * Katseta loodud alamprogrammi mitmesuguste sõlmede ja servade arvu juures. Tippude seotus ja kaugus graafis Märgatav osa graafidega seotud ülesandeid uurib, kas kaks etteantud tippu on üldse omavahel seotud, kas mööda servi on võimalik teise tippu jõuda. Ning kui side olemas, siis vahel küsitakse ka siduvat teed ennast ning selle tee pikkust. Olgu siis sammudes või muudes ühikutes. Kui graafiülesandele vastus käes, siis saab juba vastusena edasi anda, kas tegemist on vahemaaga alguspunktist sihtpunkti mitme linna kaudu või inimestevahelise suhtlusega mitme tuttava kaudu. Üheks võimalikuks lahenduseks kahe sõlme vahel leiduva lühima sammude arvuga tee leidmiseks on tuua appi massiiv näitamaks iga sõlme kohta, mitme sammu kaugusel on see algsest massiivist. Algsõlme kaugus iseenese juurde on 0. Sõlmede juurde, kuhu pääseb ühe servaga, on kaugus 1. Sammu võrra kaugemate sõlmede juurde saab kauguseks kirjutada 2 jne. Sõlmede kaugus, kuhu pole üldse võimalik jõuda, tuleb tähistada mõne võimatu väärtusega. Näiteks miinus 1ga. Esialgu võiks sellega tähistada kõik väärtused kaugustemassiivis. Edaspidi saab ligipääsetavate tippude kaugustele hakata väärtusi jagama. Algustipu saab kaugustemassiivis kergesti tähistada 0-ga. Algustipu järjekorranumber on meil paratamatult olemas. Edasi tuleks tähistada ühtedega kõikide tippude kaugused, kuhu pääseb algtipust ühe servaga. Ja nõnda edasi. Et ei peaks iga kauguse kohta eraldi programmilõiku kirjutama, võiks aidata tsükkel. Kõigepealt võetakse uurimise alla algtipp (kaugusega 0) ning leitakse 1 serva kaugusel olevad tipud. Siis võetakse uurimise alla 1 serva kaugusel asuvad tipud ning leitakse 2 serva kaugusel asuvad tipud. Siis võetakse ette 2 serva kaugusel asuvad tipud ning leitakse 3 serva kaugusel asuvad tipud. Tsüklit on mõtet jätkata seni, kuni leiti uusi, kaugemal asuvaid tippe. Kord juba vaadeldud tippude kaugust pole enam mõtet muuta, sest paratamatult oli esimene külastus kõige lähim. Kui enam uusi ligipääsetavaid tippe ei leita, ongi massiivis kirjas iga tipu kohta, mitme sammu kaugusel see algsest tipust on. Ülesandeid * Koosta mällu kahemõõtmeline massiiv näitamaks graafis olevaid servi. * Teata, millistesse sõlmedesse pääseb sõlmest number 3. * Koosta kauguste massiiv, kus tipu number 3 kauguseks on 0, temast ühe serva kaugusel olevate tippude kauguseks märgitakse 1. * Täienda programmi nõnda, et näidatakse ka need tipud, mille kauguseks tipust 3 on 2. * Pane programm tööle tsükliga nõnda, et leitaks kõik ligipääsetavad tipud. * Trüki iga tipu kaugus servades tipust 3. Samuti teata, millistesse tippudesse pole servi pidi võimalik tipust 3 pääseda. * Katseta programmi ka teistsuguse algtipu korral. Optimeerimine Eeltoodud näites tuleb iga järgmise kaugusega tippude ploki puhul kogu kauguste massiiv uuesti läbi käia. Väikese elementide arvu puhul pole sellest probleemi. Kui aga tippude arv kasvab kümnetesse tuhandetesse (nt. veebilehestiku puhul lehekülgede arv), siis ilmneb, et arvuti teeb hulga asjatut tööd. Veidi järele mõeldes selgub, et edasi on põhjust minna vaid nendest tippudest, kuhu viimatisel kontrollimisel jõuti. St., et nt. 3 serva kaugusel asuva tipu juurde on võimalik pääseda vaid 2 serva kaugusel asuvast tipust. Nii et kui parajasti otsitakse algpunktist ühe serva kaugusel olevate tippude kaudu pääsetavaid tippe, siis on leitud tipud põhjust meelde jätta. Kui 1 serva kaugusel olevad tipud läbi vaadatud, siis järgmisel ringil otsides võib uusi tippe leida vaid viimati 2 serva kaugusele märgitud tippude kaudu. Meeldejätmiseks on mitu võimalust. Üheks mooduseks oleks näiteks kaks massiivi. Ühes on kirjas parajasti vaadatavad tipud. Teises aga vaatamisel leitud tipud. Kui parajasti vaadatavad tipud otsa saavad, siis tuleb edasiminekuteid otsida leitud tippude hulgast. Nii võib leitud tippude massiivi muuta uuritavate tippude massiiviks ning sealtkaudu edasiminekuteid uurida. Uued leitud tipud paigutatakse siis jällegi eelnevalt tühjendatud leitud tippude massiivi. Sama töö teeb ära laiemaltki kasutatav võimalus nimega "järjekord". Et samas järjekorras, kui siia elemente lisatakse, samas järjekorras ka võetakse. Et kes seisab esimesena sabasse, saab ka esimesena oma kauba kätte. Nii on võimalik panna leitud tippe järjekorra lõppu ning uusi uuritavaid tippe võtta järjekorra eest. Nii on kindel, et lähemad tipud on enne läbi uuritud, kui kaugemate tippudeni jõutakse. Sest lähemad tipud satuvad lihtsalt varem järjekorda. Ülesandeid * Koosta tühi täisarvude massiiv hoidmaks leitud ja uurimist ootavate tippude järjekorranumbreid. Massiivi pikkuseks olemasolevate tippude arv, sest rohkem kui korra pole siin näites mõtet ühte tippu uurida - tema kaugus algpunktist on juba teada. * Loo muutujad "uurimisalgus" ja "uurimisots". Esimene tähistab järgmisena välja võetava ning teine viimati pandud elemendi järjekorranumbrit. Säti väärtused algul nõnda, et järjekord oleks tühi. * Loo käsklus järjekorda väärtuse lisamiseks. Selle tulemusena suureneb "uurimisots" ning vastavale kohale massiivis pannakse lisatud element. * Loo käsklus järjekorra algusest väärtuse küsimiseks koos eemaldamisega - "uurimisalgus" suureneb ühe võrra. * Loo käsklus järjekorras olevate elementide väljatrükiks. * Loo käsklus kontrollimaks, kas järjekorras leidub veel elemente. * Katseta testprogrammi abil arvude lisamist järjekorda ning eemaldamist sealt. * Täienda eelnevalt loodud algtipust kaugust määravat programmi nõnda, et uute seotud tippude otsimisel võetakse uuritavad tipud järjekorrast ning lisatakse leitud tipud järjekorda. Töö lõppeb, kui järjekord saab tühjaks. Tagasitee Eelneva abil saime küll teada iga elemendi kauguse alguspunktist. Või siis teate, et punktid polegi ühendatud. Tee enese leidmiseks tuleb aga andmeid talletada. Olemasoleva näite juures on lihtsam talletada teed lõpust algusesse kui algusest lõppu. Kui iga kaugemal asuva tipu juurde märkida, millise viimatise tipu kaudu sinna algtipust jõuti, siis ongi tee käes. Selleks tuleb teha juurde uus massiiv, milles iga uue sõlmeni jõudmisel märgitakse, kust sõlmest sinna jõuti. Kui soovida tagasiteed välja trükkida, siis saab kõigepealt trükkida lõpppunkti. Siis leiab tagasitee massiivist viimasesse punkti viinud sõlme järjekorranumbri ning saab selle välja trükkida. Siis aga omakorda tollest eelviimasest sõlmest eelmise leida ja taas trükkida. Kuni lõpuks jõutakse algusesse, kus eritunnuse (nt. taas miinus 1) järgi leitakse, et enam pole kuhugi tagasi minna ning ollaksegi alguspunktis. Ülesandeid * Loo tagasitee viidete jaoks täisarvumassiiv. Täida see otsingu algul miinus ühtedega. * Iga kord uue sõlme leidmisel jäta ühes selle juurde märgitud kaugusele meelde tagasitee massiivis ka sõlme number, kust kaudu uue sõlmeni jõuti. * Pärast kauguste arvutamist elemendist nr. 3 trüki ekraanile nii kauguste massiiv kui tagasitee massiiv. Kontrolli väärtuste õigsust. * Trüki tee ning tee pikkus etteantud tippude vahel või teata ühenduse võimatusest. * Võimalda tee trükkida ka vastupidises järjekorras, see tähendab algelemendist lõppelemendi poole. Selleks tuleb teel paiknevate sõlmede numbrid enne trükkimist meelde jätta ning siis vastupidises järjekorras väljastada. * Koosta kahemõõtmeline massiiv, kus oleksid kirjas kõikide tippude kaugused kõikidest teistest tippudest. Kontrolli tulemuse õigsust. * Loo sarnane massiiv ka tee leidmiseks kõikide võimalike tipupaaride vahel. Kontrolli samuti tulemust. * Loo rakendus, mille kaudu on võimalik määratud tippude vahelisi kaugusi ning teid küsida. Kodutöö * Koosta reaalelu sugemetega ülesanne, mille lahendamiseks saab loodud teeotsinguvahendit kasutada. Esitage näidislahendus. Lahendage ka ühe naabri ülesanne. Soovitavad ülesande keerukuse näited * Tekstifailis on kirjas inimeste nimed. Iga nime järel on kirjas nimede loetelu, keda ta tunneb. Eeldame, et puuduvad samanimelised inimesed - neil vähmalt ühele on eristamiseks mõeldud hüüdnimi. Tekstifaili viimasel real on kaks nime. Leia, kas nende puhul võib teade tuttavate kaudu ühelt teisele jõuda. Jõudmisvõimaluse korral väljasta võimalik teate liikumistee tuttavate vahel. * Firma veebilehestikus on kõik lehed seotud viidetega nõnda, et kui ühelt lehelt pääseb teisele, siis pääseb ka teiselt viitega esimesele. Tekstifaili algul on kirjas failide nimed, millest veebilehestik koosneb. Esimesel real on avalehe nimi. Edasi järgnevad omavahel seotud lehtede paarid, üks paar igal real. Leia lehed, kuhu pole võimalik avalehelt jõuda. Leia lehed, kuhu jõuab avalehelt kahe või vähema hiireklõpsuga.