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:49] – Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [17.11.2022 09:24] (aktuell) – [Bearbeiten - Panel] Frank Schiebel | ||
---|---|---|---|
Zeile 59: | Zeile 59: | ||
<panel title=" | <panel title=" | ||
Möchte man eine Knoten- oder Kantenliste sortieren oder den größten/ | Möchte man eine Knoten- oder Kantenliste sortieren oder den größten/ | ||
- | Zunächst holt man sich eine Liste der Knoten/ | + | Zunächst holt man sich eine Liste der Knoten/ |
<code java> | <code java> | ||
Zeile 76: | Zeile 76: | ||
</ | </ | ||
+ | Benötigt man eine andere Sortierung, kann man die Klasse Comparator benutzen und angeben nach welchem Wert sortiert werden soll: | ||
+ | |||
+ | <code java> | ||
+ | import java.util.Comparator; | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | // | ||
+ | knoten.sort(Comparator.comparing(Knoten:: | ||
+ | // | ||
+ | knoten.sort(Comparator.comparing(Knoten:: | ||
+ | </ | ||
</ | </ | ||
<panel title=" | <panel title=" | ||
Zeile 98: | 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 (Tiefensuche) | + | toDo.add(0, n); //füge am Anfang der Liste hinzu |
// oder | // oder | ||
- | // toDo.add(n) | + | // toDo.add(n) |
} | } | ||
} | } | ||
Zeile 108: | Zeile 120: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Alternativ kann man statt einer ArrayList auch die ADTs Stapel (Stack) oder Schlange (Queue) benutzen, die automatisch das Einfügen an der richtigen Stelle übernehmen. | ||
+ | |||
+ | </ | ||
+ | <panel title=" | ||
+ | Standartmäßig wird beim Start des Algorithmus einmal die Methode '' | ||
+ | |||
+ | <code java> | ||
+ | import java.util.ArrayList; | ||
+ | import java.util.Collections; | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | public void fuehreAlgorithmusAus() { | ||
+ | rekursiveMethode(getStartKnoten()); | ||
+ | } | ||
+ | |||
+ | public void rekursiveMethode(Knoten k){ | ||
+ | // Abbruchbedingung | ||
+ | if (k.isMarkiert()) { | ||
+ | // Ausführung unterbrechen | ||
+ | step(); | ||
+ | return true; | ||
+ | } else { | ||
+ | // Aktion mit Knoten durchführen, | ||
+ | k.setMarkiert(true); | ||
+ | // Ausführung unterbrechen | ||
+ | step(); | ||
+ | |||
+ | // Rekursiver Aufruf mit allen Nachbarknoten | ||
+ | for(Knoten nachbar : g.getNachbarknoten(k)) { | ||
+ | rekursiveMethode(nachbar); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | <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(" | ||
+ | </ | ||
+ | |||
+ | {{: | ||
</ | </ | ||
</ | </ |