Teknillinen korkeakoulu
Tietojenkäsittelyopin laboratorio
Tik-76.122 Tietorakenteet ja algoritmit
Demotehtävä

Viikon vinkki: Piirrä verkko paperille ennenkuin ratkaiset tehtävän!

Tehtävä 4.1 (1 pistettä)

Tarkastellaan suuntaamatonta verkkoa, johon kuuluvat annetut särmät (edges). Siirrä särmät annetussa järjestyksessä verkon seuraajaluetteloon (list).

Selainohjelmasi ei osaa suorittaa Java 1.0.2 ohjelmasia (appletteja)!

Mahdollinen syy: Java-ohjelmasten suorittaminen on estetty selainohjelmassasi. Tällöin niiden suorittaminen tulee sallia ennekuin tehtäviä pääsee ratkomaan. Esimerkiksi Netscape Navigator -selainohjelmassa Java-ohjelmasten suoritus sallitaan Options-valikosta (joko kohdasta Network Preferences/Languages tai Security Preferences/General riippuen versiosta).

Mikäli selainohjelmasi ei tue Java-ohjelmasia, ei sillä tehtäviä voi ratkaista WWW-sivujen kautta. Tällöin tulee käyttää joko sellaista selainohjelmaversiota, joka tukee Javaa tai sähköpostia tehtävien palautukseen.

Esimerkki

Jos annettuna särmät (edges) ovat järjestyksessä 

	AG AB AC LM JM JL JK ED FD HI FE AF GE,

saadaan näistä seuraajaluettelo: 

		A:  F  C  B  G
		B:  A
		C:  A
		D:  F  E
		E:  G  F  D
		F:  A  E  D
		G:  E  A
		H:  I
		I:  H
		J:  K  L  M
		K:  J
		L:  J  M
		M:  J  L

Huom: A laitetaan ensimmäisenä G:n listalle ja on siksi joutunut oikeanpuolimmaiseksi. Sama pätee G:lle A:n listalla. Ensin laitettu on siis listan viimeisena.