bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1341 / inda10 / Vårens uppgifter / Uppgift 7

Uppgift 7 våren 2011

Uppgiften ska lämnas till din övningsledare på övningen den 25/3.

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 den här texten om grafer.

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 Θ(n2) tid för en sammanhängande graf med n hörn om grafen representeras med en närhetsmatris.

Bekanta dig med koden i Uppg7Skelett.zip 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.zip.)
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.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2011-02-18