Aufgabenblatt 3 | |
Ausgabetermin: | 6.11.00 |
Abgabetermin: | Montag d. 13.11. bis 24 Uhr per Email an die Übungsgruppenleiter |
Motivation: | Begleitende Übungen zum Vorlesungsthema "Dynamische Datenstrukturen". Dynamische Strukturen beim Problemlösen durch Suchen. |
Aufgabe 1: | Implementieren Sie die Klasse Graph mit den folgenden Operationen
auf gerichteten Graphen (s. Vorlesung):
empty : => graph insertNode : graph x node => graph insertEdge : graph x node x node => graph deleteNode : graph x node => graph deleteEdge : graph x node x node => graph successors : graph x node => list predecessors : graph x node => list containsNode : graph x node => bool containsEdge : graph x node x node => bool isempty : graph => bool getNodes : graph => list Bedenken Sie, daß ein Graph aus mehreren nicht verbundenen Teilgraphen bestehen kann. Testen Sie Ihre Implementation mit dem Graphen: (Knoten: Nachfolger) 1: 2 3 2: 1 7 3: 3 6 2 4: 5 5: 4 6: 7 7: 6 5 Punkte |
Aufgabe 2: | Implementieren Sie eine Funktion ShortestPath, die in
einem Graphen den kürzesten Pfad zwischen zwei beliebigen Knoten ermittelt
und als Knotenliste ausgibt. Falls kein Pfad existiert, soll eine leere
Liste ausgegeben werden. Wenden Sie ShortestPath auf die Knotenpaare (1
6) und (4 7) im Graphen von Aufgabe 1 an.
5 Punkte |
Abzugebende
Dokumente |
Aufgabe 1: Kommentierter Quellcode, Testumgebung
Aufgabe 2: Kommentierter Quellcode, Testumgebung Schicken Sie bitte Ihre Dokumente - ein Exemplar je
|