Hallo Jungs!
Ich beschäftige mich gerade mit folgendem Problem: Demnächst müssen wir einen Graphen, Baum und binären Baum so implementieren, dass wir als Superklasse einen Graphen haben. Ein Graph enthält ja Knoten und Kanten. Er kann gerichtet oder ungerichtet sein, wie auch Zyklen haben. Jeder Baum ist ein azyklischer gerichteter Graph. Das heißt, man muss die Klasse Baum von der Klasse Graph ableiten können, da ein Baum einen Graphen spezialisiert. Von der Klasse Baum kann man dann auch die Klasse BinärerBaum ableiten, denn dieser spezialisiert den allgemeinen Baum.
Man soll natürlich soviel Code wie möglich von den 'oberen' Klassen erben. In der Klasse BinärerBaum müssen wir dann auch Methoden haben wie Knoten löschen oder den binären Baum in inorder (oder auch preorder) zu traversieren.
Unser Professor hat uns gesagt, dass es auf jeden Fall sinnvoll ist, dass die Superklasse Graph abstrakt sein muss. Diesen Sinn habe ich bisher nicht ganz verstanden. Natürlich kann man in der abstrakten Klasse Graph notwendige Methoden nennen und diese dann in den Unterklassen implementieren.
Ich versuche gerade, mir ein Konzept zu überlegen, wie ich es sinnvoll implementiere. Ein Ziel ist auch zum Beispiel, in der Unterklasse BinärerBaum eine Methode zu schreiben, die den Baum in einen balancierten Zuastand bringt, oder ihn derart sortiert, dass er anschließend einen Heap darstellt.
Folgende Überlegungen habe ich mir schon gemacht: Jeder Knoten im Graph besitzt einen Inhalt (zB einen String) und eine Nummer, sodass man alle Knoten durchnummerieren kann. Mann kann jetzt eine Klasse Knoten schreiben, die der Graph verwendet.
Für einen Graphen müssen folgende Methoden/Attribute zur Verfügung stehen:
boolean istGerichtet // legt die Unterklasse fest
addKnoten(Knoten k)
addKanten(int von, int bis, int kosten) // 'von' und 'bis' sind die Nummern der Knoten; Kosten ist der Wert der Kannte(kann man auch weg lassen)
löscheKnoten(Knoten k)
löscheKante(int von, int bis)
getKosten(int von, int bis) // liefert die Kosten einer Kante
getInhalt(Knoten k)
Den Graphen selbst könnte man mit Hilfe einer Adjazenzmatrix oder -liste implementieren.
Ich hoffe, das war nicht zu durcheinander. Habt ihr sowas in der Art schon mal gemacht? Ich würde mich sehr freuen, wenn ihr mir helfen würdet.
Johannes
Ich beschäftige mich gerade mit folgendem Problem: Demnächst müssen wir einen Graphen, Baum und binären Baum so implementieren, dass wir als Superklasse einen Graphen haben. Ein Graph enthält ja Knoten und Kanten. Er kann gerichtet oder ungerichtet sein, wie auch Zyklen haben. Jeder Baum ist ein azyklischer gerichteter Graph. Das heißt, man muss die Klasse Baum von der Klasse Graph ableiten können, da ein Baum einen Graphen spezialisiert. Von der Klasse Baum kann man dann auch die Klasse BinärerBaum ableiten, denn dieser spezialisiert den allgemeinen Baum.
Man soll natürlich soviel Code wie möglich von den 'oberen' Klassen erben. In der Klasse BinärerBaum müssen wir dann auch Methoden haben wie Knoten löschen oder den binären Baum in inorder (oder auch preorder) zu traversieren.
Unser Professor hat uns gesagt, dass es auf jeden Fall sinnvoll ist, dass die Superklasse Graph abstrakt sein muss. Diesen Sinn habe ich bisher nicht ganz verstanden. Natürlich kann man in der abstrakten Klasse Graph notwendige Methoden nennen und diese dann in den Unterklassen implementieren.
Ich versuche gerade, mir ein Konzept zu überlegen, wie ich es sinnvoll implementiere. Ein Ziel ist auch zum Beispiel, in der Unterklasse BinärerBaum eine Methode zu schreiben, die den Baum in einen balancierten Zuastand bringt, oder ihn derart sortiert, dass er anschließend einen Heap darstellt.
Folgende Überlegungen habe ich mir schon gemacht: Jeder Knoten im Graph besitzt einen Inhalt (zB einen String) und eine Nummer, sodass man alle Knoten durchnummerieren kann. Mann kann jetzt eine Klasse Knoten schreiben, die der Graph verwendet.
Für einen Graphen müssen folgende Methoden/Attribute zur Verfügung stehen:
boolean istGerichtet // legt die Unterklasse fest
addKnoten(Knoten k)
addKanten(int von, int bis, int kosten) // 'von' und 'bis' sind die Nummern der Knoten; Kosten ist der Wert der Kannte(kann man auch weg lassen)
löscheKnoten(Knoten k)
löscheKante(int von, int bis)
getKosten(int von, int bis) // liefert die Kosten einer Kante
getInhalt(Knoten k)
Den Graphen selbst könnte man mit Hilfe einer Adjazenzmatrix oder -liste implementieren.
Ich hoffe, das war nicht zu durcheinander. Habt ihr sowas in der Art schon mal gemacht? Ich würde mich sehr freuen, wenn ihr mir helfen würdet.
Johannes