Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [14.11.2022 17:56] – [Bearbeiten - Panel] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [17.11.2022 09:24] (aktuell) – [Bearbeiten - Panel] Frank Schiebel | ||
---|---|---|---|
Zeile 110: | Zeile 110: | ||
// füge alle nicht besuchten Nachbarknoten der Liste hinzu | // füge alle nicht besuchten Nachbarknoten der Liste hinzu | ||
- | for(Knoten nachbar : g.getNachbarKnoten(k)) { | + | for(Knoten nachbar : g.getNachbarknoten(k)) { |
if(!nachbar.isMarkiert() && !toDo.contains(nachbar)) { | if(!nachbar.isMarkiert() && !toDo.contains(nachbar)) { | ||
toDo.add(0, n); //füge am Anfang der Liste hinzu | toDo.add(0, n); //füge am Anfang der Liste hinzu | ||
Zeile 150: | Zeile 150: | ||
// Rekursiver Aufruf mit allen Nachbarknoten | // Rekursiver Aufruf mit allen Nachbarknoten | ||
- | for(Knoten nachbar : g.getNachbarKnoten(k)) { | + | for(Knoten nachbar : g.getNachbarknoten(k)) { |
rekursiveMethode(nachbar); | rekursiveMethode(nachbar); | ||
} | } | ||
Zeile 158: | Zeile 158: | ||
</ | </ | ||
+ | </ | ||
+ | |||
+ | <panel title=" | ||
+ | |||
+ | Backtracking lässt sich am leichtesten rekursiv implementieren. | ||
+ | |||
+ | <code java> | ||
+ | import java.util.ArrayList; | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | public void fuehreAlgorithmusAus() { | ||
+ | // Starte Backtracking mit Startknoten | ||
+ | ArrayList< | ||
+ | // Wenn Lösung gefunden, dann anzeigen | ||
+ | if(loesung != null) g.restoreStatus(loesung); | ||
+ | step(); | ||
+ | } | ||
+ | |||
+ | public ArrayList< | ||
+ | // Bisher keine Lösung gefunden | ||
+ | ArrayList< | ||
+ | |||
+ | // Abbruchbedingung: | ||
+ | if (k.isMarkiert()) { | ||
+ | step(); | ||
+ | loesung = g.saveStatus(); | ||
+ | } | ||
+ | // Rekursionsschritt | ||
+ | else { | ||
+ | // aktuellen Zustand sichern | ||
+ | ArrayList< | ||
+ | |||
+ | // Probiere alle Möglichkeiten | ||
+ | // hier alle nicht markierten, ausgehenden Kanten | ||
+ | ArrayList< | ||
+ | ArrayList< | ||
+ | |||
+ | for(Kante ausgehendeKante : nichtMarkiert) { | ||
+ | // Führe Aktionen aus und anzeigen | ||
+ | k.setMarkiert(true); | ||
+ | ausgehendeKante.setMarkiert(true); | ||
+ | step(); | ||
+ | |||
+ | // Rekursion | ||
+ | Knoten nachbar = ausgehendeKante.getAnderesEnde(k); | ||
+ | loesung = backtracking(nachbar); | ||
+ | |||
+ | // Rückschritt | ||
+ | g.restoreStatus(aktuellerZustand); | ||
+ | step(); | ||
+ | if(loesung != null) break; | ||
+ | } | ||
+ | } | ||
+ | return loesung; | ||
+ | } | ||
+ | </ | ||
+ | </ | ||
+ | <panel title=" | ||
+ | Um Informationen oder Ergebnisse eigener Algorithmen auszugeben, bietet der Graphentester drei Möglichkeiten an: | ||
+ | |||
+ | ==== Java Konsole ==== | ||
+ | |||
+ | Man kann mit '' | ||
+ | |||
+ | ==== melde() ==== | ||
+ | |||
+ | Mit der Methode '' | ||
+ | |||
+ | | ||
+ | |||
+ | {{: | ||
+ | |||
+ | ==== info() ==== | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Mit Hilfe der Methoden '' | ||
+ | |||
+ | Beispiel: | ||
+ | |||
+ | <code java> | ||
+ | info(" | ||
+ | infoIndentMore(); | ||
+ | for(Knoten k: alleKnoten) { | ||
+ | int Eingangsgrad = g.getEingehendeKanten(k).size(); | ||
+ | info(" | ||
+ | k.setWert(Eingangsgrad); | ||
+ | } | ||
+ | infoIndentLess(); | ||
+ | info(" | ||
+ | </ | ||
+ | |||
+ | {{: | ||
</ | </ | ||
</ | </ |