INDA - Övning 7 våren 2007
Uppgiften ska lämnas till din övningsledare på övningen den 22/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 i katalogen /info/inda06/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
2007-02-13
|