Kurzbeschreibung:

Allgemeine Hinweise:

• Das Beispiel dieser Runde objektorientiert und als package zu lösen. Nachdem Sie das Programm mittels Dialogprogramm abgegeben haben, gehen Sie zu einem Tutor. Der Tutor überprüft, ob Sie Ihr Programm spezifikationsgemäß programmiert haben.
• Unmittelbar nach der erfolgreichen Abgabe am Dialogprogramm können sie bereits die nächste Runde abholen.
• Sie haben Lösungen (und Spezifikationen) aus der 3. Runde von anderen Studenten erhalten. Testen Sie alle mitgelieferten Lösungen und wählen Sie eine Lösung aus, die Ihnen hinsichtlich Lesbarkeit, Programmierstil, Korrektheit und Verwendbarkeit am besten erscheint.
• Merken Sie sich die Lösungsnummer des ausgewählten Beispieles für die Abgabe. Diese Nummer müssen Sie bei der Abgabe angeben. Geben Sie nur jene Lösungsnummer an, die Sie auch wirklich ausgewählt haben.
• Erstellen Sie für alle Lösungen zu diesem Beispiel (siehe: "Abzugebende Files") ein File mit dem Namen <number>.txt. und schreiben in dieses File ein Review (=Kritik) zu der Lösung. Diese Reviews erhalten dann die TeilnehmerIn von dem/der die Lösung stammt. Beachten Sie das bitte bei der Form Ihrer Kritik.
• Sie können für die Lösung der gewählten Aufgabe eine oder mehrere Klassen programmieren. Die Klasse main.java muß aber die Methode main enthalten. Weiters müssen alle anderen abgegebenen Klassenfiles in Verzeichnis Ggraphzu vorliegen, Pfadangaben sind nicht gestattet.
• Achten Sie auf die korrekten Konventionen der Groß/Kleinschreibung bei Klassen und Methoden!
• Falls Ihre Lösung einen Exit Code zurueckliefert, so achten Sie darauf, dass dieser den Wert 0 hat. Bei allen anderen Werten können Probleme bei der Bewertung und in weiterer Folge unbeabsichtigte Punkteabzüge auftreten.
• Ihre Lösung darf nur genau jene Ausgabedaten liefern, die in der Spezifikation verlangt werden. Die Ausgaben Ihrer Lösung werden automatisch mit Referenzdaten verglichen; etwaige Abweichungen führen zu Punkteabzügen!
• Testen Sie Ihre Lösung vor der Abgabe mit der mitgelieferten Eingabedatei. Geben Sie Ihre Lösung erst ab, wenn die Ausgaben Ihrer Lösung mit der ebenfalls mitgelieferten Ausgabedatei übereinstimmen! Testen Sie Ihre Lösung auch mit anderen Eingabedaten.
• Verwenden Sie nur das von uns mitgelieferten Package eprog für Ihre Ein/Ausgaben. Klassen, die Packages oder Klassen ausserhalb der verwendeten Übungsumgebung (Java2, Standard Edition, Version 1.3.1_1) verwenden, können von uns nicht getestet werden und werden daher mit 0 Punkten bewertet!
• Schreiben Sie Ihre Klasse(n) möglichst allgemein und kommentieren Sie diese gut. Erstellen Sie weiters eine übersichtliche und verständliche Dokumentation. Damit erhöhen Sie Ihre Chancen, daß andere Studenten in der nächsten Runde Ihre Lösung wählen und Ihnen damit zu Zusatzpunkten verhelfen!

Aufgabenstellung:

Überprüfen Sie einen solchen gerichteten Graphen auf seinen Zusammenhang.

Lesen Sie solange Strings ein, bis die Eingabe durch den String "0" abgeschlossen wird. Die Strings dürfen dabei nur aus Buchstaben bestehen.

Jeder String soll einen Knoten eines gerichteten Graphen darstellen, wobei das erste Zeichen des Strings den Knoten selbst bezeichnet, die darauffolgenden Zeichen sollen Knoten spezifizieren, zu denen eine gerichtete Verbindung besteht.

Testen Sie, ob der so eingegebene Graph ein zusammenhängender Graph ist (von jedem Knoten führt mindestens ein Weg zu jedem anderen Knoten).

Bauen Sie mit den eingelesenen Daten eine "Adjazenzliste" auf:

In der ersten Zeile befinden sich alle Knoten des Graphen. Darunter sind alle benachbarten Knoten angeführt, zu denen eine Kante weist.

Für die Überprüfung schreiben Sie eine am besten eine rekursive Prozedur, die ausgehend von einem Knoten einen Weg (über einen oder mehrere andere Knoten) sucht.
(Achtung: Bereits besuchte Knoten sind zu markieren, da sonst die Gefahr einer endlosen Rekursion besteht!)
Tip: Wenn ausgehend von einem Knoten alle möglichen Wege (bis es keine Fortsetzung mehr gibt) rekursiv durchlaufen werden und danach festgestellt wird, daß alle anderen Knoten bereits besucht wurden, so gibt es zwangsläufig einen Weg zu jedem anderen Knoten.
(Achtung: Wenn ein Weg von A nach B existiert, muß deshalb noch kein Weg von B nach A führen (gerichteter Graph!)).

Eingabedaten:

Die Reihenfolge der eingegebenen Knoten und deren Verbindungen muß nicht geordnet sein (d.h. "B" muß nicht unbedingt nach "A" folgen).
Wenn von einem Knoten keine Kanten wegführen, muß er trotzdem als einzelner Buchstabe angeführt werden.
Es darf im Alphabet kein "Loch" entstehen, d.h. wenn es einen Knoten "C" gibt, dann muß es auch einen Knoten "B" geben.
Jeder Knoten darf nur einmal in der Eingabe als Ausgangsknoten auftreten.

Ausgabedaten:

Fehlerbehandlung:

Beispiele:

Eingabedaten

ABD ACB BCD DB 0 ABD BC CB DA 0 ABD BCD CB DA 0

Ausgabedaten

FALSCHE EINGABE NEIN JA

Testen:

java Main < Ggraphzu.i1 > Ggraphzu.out1

Das erzeugte File Ggraphzu.out1 können Sie dann mit dem mitgelieferten Outputfile Ggraphzu.o1 vergleichen.