Graph - Verständnisprobleme

[paco89]

hallo, ich hab folgende aufgabe zunächst durchgelesen und hab mir gedanken dazu gemacht. in der aufgabenstellung verwirren mich die 3 klassen.

also bevor ich mit den aufgaben anfangen wollte, wollte ich nur mal sicherstellen wie das mit den klassen zu verstehen ist. die klassen und die einleitung der aufgabe habe ich als anhang gepostet. die teilaufgaben hab ich zunächst einmall weggelassen, weil ich erst wissen wollte, wie das mit den klassen gemeint ist.

also die bilder habe ich hochgeladen. mich verwirren die beiden klassen EdgeList und Edge. wenn ich es richtig interpretiert habe geht es in der klasse Edge doch nur von wo bis wo die kante zeigt, oder?
beim erzeugen eines objekts der klasse edge bekommt der konstruktor die parameter int s und int e. die stehen dann doch für die knoten.

aber die Klasse EdgeList ? ich verstehe einfach den sinn dieser klasse nicht. ist das die klasse die die mengen der kanten beschreibt?

auf jeden fall kann ich mir das nicht so ganz erklären und deshalb ist jede hilfe willkommen.

 

[Firephoenix]

Fang erstmal bei der Klasse Edge an:
Jede Edge hat einen Anfang und ein Ende (die Knotennummern).
(Beispiel aus dem Bild: Die Edge(1,2) würde von Knoten 1 nach unten Links zum Knoten 2 gehen.

Wie in der Aufgabe auch steht werden die Kanten jetzt als verkettete Liste gespeichert (google hilft im zweifelsfall).
Dafür ist die Klasse EdgeList.
Jede EdgeList speichert eine Edge (aktuelles Element) und eine weiter Liste (nachfolger).
Ich glaube nicht, dass es möglich ist damit direkt den Graph zu modellieren, das geschieht implizit über die Nummern der Kanten.
Denn die Kante 1,2 hat z.b. 3 Nachfolger (2,0) , (2,1) und (2,3) - das kannst du mit der einfachen verketteten Liste nicht darstellen.

Statdessen speicherst du einfach alle Kanten in die Liste - die Reihenfolge ist ja offenbar nicht festgelegt.

Gruß

 

[M_Schaffrath]

Ich verstehe es so, dass Edge eine Kante im gerichteten Graphen modelliert, indem es den Index des Anfangs- und des Endknoten speichert. EdgeList ist ein einzelnes Element einer verketteten Liste von Edges, die eine Edge und deren Nachfolger (also der nächste Weg im Graphen) enthält. Graph wiederum enthält das erste Element einer solchen Liste, von dem man sich über die Nachfolger zu jedem Element in der Liste durchhangeln kann, um so den Graphen zu durchlaufen.

Nehmen wir einmal an, das hier wäre der Graph mit drei Knoten und zwei Kanten:

A - B - C

Dann wären im Edge-Objekt für die erste Kante die Werte 'A' und 'B' gespeichert.
Im Edge für die zweite Kante die Werte 'B' und 'C'.

In der Liste enthielte das zweite Element nur die zweite Kante ohne Nachfolger. Das erste Element enthielte die erste Kante und die zweite Kante als Nachfolger.

Der Graph enthielte einen Verweis auf das erste Listenelement.

 

[paco89]

ja, okay, so ungefähr hatte ich es mir auch gedacht.....jetzt komme ich zurecht....

 

[paco89]

also ich musste in der ersten teilaufgabe eine methode schreiben, die die anzahl der kanten des graphen bestimmt, und ich habe folgendes aufgeschrieben:

public int anzahlKanten()
{
	return anzahlKanten(this.edges);
}

private static int anzahlKanten(Graph g)
{
	if (g!=null)
		return 0;
		
	if (g.next!=null)
		int ergebnis=1;
		
	return ergebnis + anzahlKanten(g.next);
}

ich durfte hie keine schleifenkonstrukte verwenden nur rekursion. meint ihr, ich habs richtig gelöst?