UE Algorithmen 2 - Uebung 8

Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

8. Übung - abzugeben am 1. 12. 1998 in Ihrer Übungsgruppe

8.a Kruskal

Gegeben sei der ungerichtete Graph V={0,1,2,3,4,5,6,7,8} mit den Kanten E={[0,1]₁₆, [0,2]₄, [1,6]₁₃, [2,3]₁₁, [2,5]₄, [2,6]₉, [3,4]₅, [3,5]₆, [4,7]₄, [4,8]₃, [5,6]₁₂, [5,7]₁₅, [6,7]₆} samt tiefgestellten Kantenbewertungen.
Erstellen Sie nach dem Algorithmus von Kruskal den minimal spannenden Baum.

8.b Programm

Implementieren Sie ein Modul mit folgender Interface Definition bzw. Implementierungshilfe:


MODULE Graph;
  TYPE
    ValueT* =LONGINT;  (*Bewertungs-Typ*)
    NodeNoT*=LONGINT;  (*Knotennummer-Typ*)
    GraphT* =RECORD
       a (*Adjazenzmatrix*), 
       w (*Wegematrix*), 
       m (*Orientierungsmatrix für Bsp. c*):
         POINTER TO ARRAY OF ARRAY OF LONGINT;
       ...............
    END; (*RECORD*)

  PROCEDURE (VAR g:GraphT) Init*(v:INTEGER);
    (* v=Anzahl der Knoten im Graphen
    *) 
  PROCEDURE (VAR g:GraphT) CleanUp*();
    (* Freigabe des Graphens = Freigabe des dynamisch
       allokierten Speicherplatzes
    *)
  PROCEDURE (VAR g:GraphT) SetEdge*(x,y:NodeNoT; value:ValueT);
    (* Kante x,y mit Bewertung value in den gerichteten
       Graphen aufnehmen
    *)
  PROCEDURE (VAR g:GraphT) PrintAdj*();
    (* Ausgabe der Adjazenzmatrix der Kantenbewertungen.
    *)
  PROCEDURE (VAR g:GraphT) Warshall*();
    (* Anwenden des Alg. von Warshall auf den gewichteten, 
       gerichteten Graphen g.
    *)
  PROCEDURE (VAR g:GraphT) PrintWays*();
    (* Ausgabe der Wegematrix - kürzeste Weglängen
       für alle Wege von i nach j.
    *)
END Graph;

8.c Programm

Erweitern Sie das Modul aus Bsp. b um folgende Funktionalität:


  PROCEDURE (VAR g:GraphT) PrintOrientation*();
    (* Ausgabe der Orientierungsmatrix - gibt für jeden
       kürzesten Weg [x,y] an, welches der erste
       Zwischenknoten am Weg von x nach y ist.
    *)
  PROCEDURE (VAR g:GraphT) PrintWay*(x,y:NodeNoT);
    (* Druckt den kürzesten Weg von x nach y.
       Muß folgendes anzeigen:
       Gibt es einen Weg?
       Wenn ja, welche Knoten werden dabei besucht und
       wie lange ist er?
    *)

Anmerkungen zu b und c:

Zu verwalten sind gewichtete, gerichtete Graphen
Für PrintWays, PrintOrientation und PrintWay gilt: Testtreiber (Tester) ist für richtige Reihenfolge der Ausführung verantwortlich
Besprechung der geforderten Funktionen erfolgt in der Übung
Sicherheitsabfragen nicht vergessen
Gemeinsame Abgabe von b und c

Last modified: hoermanseder@fim.uni-linz.ac.at 98-11-23