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

Tehtävä 4.2 (2 pistettä)

Tehtävässä on annettu erään suuntaamattoman verkon seuraajaluettelo. Käy verkko läpi lähtien valmiiksi annetusta solmusta. Käytä ei-rekursiivista depth-first -algoritmia, joka käyttää apunaan pinoa.

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 seuraajaluettelo olisi seuraavanlainen: 

		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

Tästä seurajaaluettelosta saataisiin seuraava pino ei-rekursiivisella depth-first-aloritmilla. Aloitus A:sta. Pinon sisältö esitetään rivinä joka vierailun (visit) jälkeen. 

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