PROTOCOL: DEEP SEARCH // PRIMM SEQUENCE

P PREDICT: Analyse

Lade die Datei 12-2-2 Tiefensuche.json in den Workspace.

Schau dir den Konstruktor der Klasse Graph und die Klasse Knoten an, ohne den Code auszuführen.

Frage 1: Wie viele Knoten werden maximal erstellt?

Frage 2: Welche Datenstruktur wird verwendet, um zu speichern, welche Knoten verbunden sind?

R RUN & I INVESTIGATE

Aufgabe: Starte das Programm (Run). Du siehst die Knoten, aber keine Verbindungen.

Wir müssen verstehen, wie die Adjazenzmatrix adja[][] funktioniert. Stell dir vor, wir verbinden 0 mit 1 und 1 mit 2.

Klicke die entsprechenden Felder in der Matrix an, die dann auf true (Grün) stehen müssen.

Hinweis: Der Graph ist ungerichtet (Hinweg = Rückweg). Zeilen = Start, Spalten = Ziel.

0

1

2

0

F

1

F

2

F

M MODIFY: Das Netz bauen

Du hast die Struktur verstanden. Zeit, den Code anzupassen.

Coding Mission 1:

Öffne kanteHinzufügen in der Klasse Graph.
Implementiere das Setzen der true Werte in das Array adja (Hin- und Rückweg!).
Gehe ins Hauptprogramm und erstelle folgende Verbindungen (siehe TODOs):

0 - 1
1 - 2
1 - 3
0 - 3
2 - 4

Führe das Programm aus. Siehst du die weißen Linien? Wenn ja, weiter.

M MAKE: Algorithmus-Logik

Wir implementieren die Tiefensuche. Bevor wir den Code schreiben, müssen wir den rekursiven Ablauf sortieren.

Bringe die Schritte der Methode tiefensucheRekursiv(knoten) in die richtige logische Reihenfolge (Drag & Drop):

Rekursiver Aufruf für den Nachbarn starten.
Schleife über alle möglichen Nachbarn (i).
Prüfen: Gibt es Kante UND ist Nachbar noch nicht besucht?
Aktuellen Knoten als 'besucht' markieren.
Basisfall prüfen: Bin ich am Ziel? Wenn ja -> return true.

M MAKE: Die Start-Methode

Jetzt wird programmiert. Wir beginnen mit der Wrapper-Methode tiefensuche(start, ziel).

Fülle diesen Lückentext aus, um den Code für deine IDE vorzubereiten:

void tiefensuche(int start, int ziel) { // 1. Gedächtnis erstellen [] besucht = new [anzKnoten]; // 2. Rekursion starten gefunden = (start, ziel, besucht); if (gefunden) { println("Weg gefunden!"); } }

M MAKE: Die Rekursion

Das Finale. Implementiere nun die Methode tiefensucheRekursiv komplett in Java.

Die Anforderungen an deinen Code:

Markiere besucht ???.
Wenn ?? ziel: Gib ??? zurück.
Laufe durch alle(?) Knoten.
Wenn adja ? UND !??:
-> Rufe rekursiv auf. Wenn das Ergebnis ? ist, ????.
Wenn die Schleife durchläuft ohne Erfolg: ??

Sobald der Code kompiliert und im Hauptprogramm der Test läuft ("GEFUNDEN"), hast du die Mission erfüllt.