Blatt 12.1

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Blatt 12.1
Servus Leute,

aber was genau macht der TraversalPublicTest? Es wird ein Arrays.asList übergeben, aber mit welchen Daten ist die Liste gefüttert?
Ist in der Liste überhaupt was drin?

		for(Node n : asList)
		{
			System.out.println("Label: " + n.getLabel());
		}

Gibt mir auf jeden Fall eine leere Console zurück.
Greets

Exar

p.s.: es ist bereits der “verbesserte” Testfall von gestern 17:07 Uhr.

3

Seine Aufgabe ist es IMHO, euch zur richtigen Schnittstelle zu zwingen, damit die Tests im EST übersetzen.
Ja, die Liste ist leer: laut API von [m]Arrays.asList()[/m] ist auch nix drin…

PS: Baut euch selbst Test-Graphen ;)…

4

Das artet ja langsam in Arbeit aus, jetzt sollen wir auch noch selbst Test-Graphen bauen. :-p

5

Kann mir mal jemand mit eigenen Worten beschreiben was ich zu tun hab in den einzelnen Klassen/Methoden?

In Dfs und Bfs alle Knoten durchgehen und schon besuchte markieren?
Werd aus der Aufgabenstellung nicht ganz schlau :confused:
Danke

6

Naja erstelle einen azyklischen Graphen und lass ihn durch deine 3 Methoden laufen.
die letzte Methode soll überprüfen ob ein Zyklus vorhanden ist.

Also im Vergleich zu anderen Aufgaben von Norbert, ist diese Aufgabenstellung doch sehr eindeutig formuliert. :wink:

7

Habt ihr den Graphen gleich beim Erstellen des Streams (dfsNodeStream / bfsNodeStream) traversiert und das Ergebnis einfach nochmal zwischen gespeichert?

8

Was du machen musst ist folgendes:
Speichere dir die übergebene Liste mit den Startknoten (Achtung: Aufgabenstellung genau lesen). Jetzt musst du die gespeicherte Liste nach jedem Aufruf von getNext() anpassen und den Knoten zurückgeben, sodass man von Tiefensuche reden kann.

Beispiel DFS (aus der Aufgabenstellung):
Zu Beginn schaut die Liste so aus: [A, D]
Der erste getNext()-Aufruf sollte den Knoten A liefern und die gespeicherte Liste so verändern, dass der Inhalt der folgende ist: [B,C,D]
Der nächste Aufruf von getNext() liefert den Knoten B und verändert die Liste so: [C,D]
Dann Knoten C und [D], und schließlich D.
Ob du eine Implementierung so umsetzt oder anders, spielt keine Rolle. Hauptsache die Rückgabe der Knoten stimmt mit der Tiefensuche überein.

Edit: Hopala

9

Es ist zu empfehlen, sich in einer Datenstruktur ähnlich wie in den Folien, die zu bearbeitenden Knoten in der entsprechenden Reihenfolge zu speichern und dies bei jedem getNext()-Aufruf entsprechend anzupassen. (Ähnlich wie in gakus Beispiel oben)
Dem ein oder anderen mag es auch helfen, sich zunächst den Algorithmus für nur einen Startknoten zu überlegen.

der Graph ist azyklisch…

10

Rotes Kreuz EST für BFS und DFS. Alles private, keine Signaturen geändert, Node als Typ in Generics…

???

11

Nur um sicher zu gehen, dass dein Lob auch wirklich den Richtigen erreicht: Es geht nicht um mich, sondern um NorberT… :-p :smiley: :scared:

12

siehe Blatt 00:

… also auch so Klassen wie [m]CycleDetector[/m] oder [m]ComponentStream[/m]…

13

Vielen Dank für die Antworten schonmal :slight_smile:
Noch eine Frage was soll ich dann eigentlich erreichen einfach einen Array mit allen Nodes?
Nicht dass ich da was falsches hochlade.

14

Ich verstehe deine Frage nicht. Was willst du erreichen? Vielleicht einreichen? Ein Array?

15

Naja was halt dann im Test getestet wird.
Weil ich mach das jetzt gerade sehr auf meine eigene Art und Weise.

16

Ich versteh zwar immer noch nicht was du willst, aber ich verweise mal mit Verdacht auf den Post von JohnDoe.

PS: Ein paar Satzzeichen mehr würden deinen Sätzen echt nicht schaden.

17

so? :smiley: duckundweg :wink:

1 Like
18

Das schaut nicht schlecht aus, allerdings war das PS auf die Posts von fninja bezogen :wink: