INDA - Övning 7 våren 2006


Uppgiften ska lämnas till din övningsledare på övningen den 24/3. Jag rekommenderar att du börjar i god tid. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.


Hemuppgift
Läs om grafer, djupetförstsökning och breddenförstsökning (11.1-11.2, 11.5-11.6) i algoritmboken.


Skriftlig uppgift
Lös uppgift 11.2, 11.13 samt 11.15 i algoritmboken.

Bekanta dig med projektet i katalogen /info/inda05/Uppg7/. Din uppgift är att göra ytterligare en implementation av gränssnittet UndirectedGraph; din implementation ska avända närhetslistor. Datastrukturer och metodsignaturer är redan deklarerade i klassen ListGraph. Återanvänd testkoden från klassen MatrixGraphTest.

Testa din nya grafklass genom att skriva ett program som bygger en graf med n noder och n slumpmässigt utplacerade kanter. Programmet ska med hjälp av djupetförstsökning beräkna antalet komponenter i grafen och storleken på den största komponentet. Prova hur snabbt ditt program blir för olika värden på n, n <= 5000. Är det bäst att använda närhetsmatris eller närhetslistor i det här fallet? Varför? Förklara genom att beräkna tidskomplexiteten för DFS med närhetsmatris samt för DFS med närhetslistor.


Stefan Nilsson
2006-02-23