Göm menyn

Labb 8 -- Kontrollera om det finns en väg mellan två hörn

Labbens syfte

  • förändring av representation av grafer
  • implementera "finns väg"
  • implementera högst grad
  • uppdatera kontroll av datatyp

Att skicka in

Filen med er kod för labb 8, samt filen graph.py som ni använder i labb 8 skickas in till er labbhandledare enligt samma procedur som tidigare labbar.

Uppg 1: Förändring av representation av grafer

I labb 6 skapade vi en abstrakt datatyp för grafrepresentation. Den hade dock en stor brist - att ta reda på vilka grannar ett hörn har innebär att man måste gå igenom alla hörn i grafen. I datastrukturen som användes i labb 6 är varje hörn ihopkopplat med en lista av namn på kanter. Information om vilket hörn som denna kant leder till saknas dock.

Vi ändrar detta så att varje hörn (som nyckel i dictionaryt) istället är ihopkopplat till en lista av [kant, hörn2], där hörn2 är det hörn man kommer till om man följer kanten. För graf 1 i labb 6 får vi alltså:

[ [["a1", 0], ["a2", 0], ["a3", 0]],\
[["q1", 0], ["q2", 0]],\
{"a1":[ ["q1", "a2"], ["q2", "a3"] ],\
 "a2":[ ["q1", "a1"] ],\
 "a3":[ ["q2", "a1"] ] }

I uppgift 1 ska ni alltså ändra på den abstrakta datatypen för graf enligt ovan.

Uppgift 2: Finns väg?

Nu när det är lättare att ta reda på vilka grannar ett hörn har. Det blir därför också lättare att ta reda på om det finns en väg mellan två hörn, vilket är det ni ska göra. Implementera denna funktion som connected(graph, vertex_label1, vertex_label2).

Algoritm 9.6 från Strandh är en algoritm som tar reda på om det finns en väg mellan två hörn i en graf. Nedan följer en alternativ beskrivning av algoritmen.

Algoritmen returnerar True om det finns en väg mellan hörnen v och w, annars returneras False. Algoritmen är rekursiv och tanken är så här "om någon av mina grannar når w, så når jag w genom den grannen". Varje granne tänker likadant: "om någon av mina grannar når w, så når jag w genom den grannen".

För att inte fråga en och samma granne mer än en gång, så markerar vi varje hörn vi frågar. Om det är vissa hörn vi inte vill passera, markerar vi dem innan vi börjar undersöka om det finns en väg mellan v och w.

Nedan följer algoritmbeskrivning 9.6 från Strand:

Algoritm 9.6

  • In: En graf G och två hörn v och w som tillhör V(G)
  • Ut: Ett logiskt värde som anger huruvida det finns en stig som bara innehåller omarkerade hörn (red. anm. omarkerade från början).
  • Sidoeffekter: Vissa hörn kan markeras av exekveringen av algoritmen.
  1. Om v = w så returnera värdet sant.
  2. Använd operationen MARK_VERTEX(v) för att markera hörnet v.
  3. För varje hörn v' som är granne med v,
    1. Använd operationen VERTEX_MARKED(v') för att kontrollera huruvuda hörnet v' är markerat
    2. Om det inte är markerat:
      1. Kontrollera om det finns en stig mellan v' och w (_red. anm. här är alltså ett rekursivt anrop!)
      2. Om så är fallet, returnera sant.
  4. Om vi kommer hit, så fanns ingen stig mellan v' (granne med v), och w. Vi returnerar då falskt.

Fler detaljer finns i Strandh kap 9.

Uppgift 3: Uppdatera kontrollerna av vår abstrakta datatyp

Den sista uppgiften handlar om att ändra på hjälpfunktionerna som kontrollerar om en datastruktur är en giltig graf. I och med att strukturen för grafen förändrats, måste dessa också förändras.


Sidansvarig: Jody Foo
Senast uppdaterad: 2014-12-04