Uppgift 7 våren 2008

Uppgiften ska lämnas till din övningsledare på övningen den 27,28/3. 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 (6.1-6.3) i algoritmboken.

Skriftlig uppgift

Lös uppgift R-6.1, R-6.6, R-6.7 och R-6.8 i algoritmboken.

Bekanta dig med projektet uppg7.zip. 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.