Uppgift 7 våren 2009

Uppgiften ska lämnas till din övningsledare på övningen den 19/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 i avsnitt 3.1-3.3 i algoritmboken.

Skriftlig uppgift

Lämna in svar på följande uppgifter.

• Rita en oriktad graf med 6 hörn, 10 kanter och 2 sammanhängande komponenter. Går det att rita en graf med 5 hörn, 4 kanter och 3 komponenter?
• Låt G vara en oriktad graf som består av 8 hörn numrerade från 0 till 7 och kantmängden {(0,1), (0,3), (1,4), (2,2), (3,4), (3,5), (6,7)}.
  • Rita G.
  • Ange ordningen som hörnen besöks vid en djupetförstsökning (DFS) med start i hörn 0.
  • Ange ordningen som hörnen besöks vid en breddenförstsökning (BFS) med start i hörn 0.
  Du kan anta att grannarna till ett hörn besöks i nummerordning.
• Skulle du representera en graf med hjälp av en närhetsmatris eller med hjälp av närhetslistor i följande fall? Motivera dina svar.
  • Grafen har 1000 hörn och 2000 kanter och det är viktigt att vara sparsam med minnet.
  • Grafen har 1000 hörn och 50000 kanter och det är viktigt att vara sparsam med minnet.
  • Det är viktigt att snabbt (på konstant tid) kunna avgöra om två hörn är grannar. Om möjligt vill du också vara sparsam med minnet.
• Förklara varför DFS tar Θ(n²) tid för en sammanhängande graf med n hörn om grafen representeras med en närhetsmatris.

Bekanta dig med koden i Uppg7Skelett.jar och gör sedan ytterligare en implementation av gränssnittet UndirectedGraph; din implementation ska avända närhetslistor. Datastrukturer och metodsignaturer är redan deklarerade i klassen ListGraph. Som vanligt ska du också skriva en tillhörande testklass ListGraphTest. Återanvänd gärna testfallen från MatrixGraphTest. Du får inte ändra koden i gränssnitten UndirectedGraph, VertexIterator eller VertexAction.

• Lämna in dina nyskrivna klasser ListGraph och ListGraphTest.

Prova 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.

• Lämna in koden för detta program. (Du behöver naturligtvis inte lämna in de klasser och gränssnitt som finns färdiga i Uppg7Skelett.jar.)

Prova hur snabbt ditt program blir för olika värden på n, n <= 5000, när man använder närhetsmatris respektive närhetslistor.

• Ange antalet komponenter och den största komponentents storlek när n = 1000.
• Vilken datastruktur är bäst 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.