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:42] – [Bearbeiten - Panel] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [17.11.2022 09:24] (aktuell) – [Bearbeiten - Panel] Frank Schiebel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Hilfestellung zur Programmierung mit dem Graphentester ====== | ====== Hilfestellung zur Programmierung mit dem Graphentester ====== | ||
+ | |||
+ | <WRAP center round info 96%> | ||
+ | **[[https:// | ||
+ | </ | ||
+ | |||
< | < | ||
<panel title=" | <panel title=" | ||
Soll der Algorithmus mit allen Knoten des Graphen etwas Bestimmtes machen, dann verwendet man die Methode '' | Soll der Algorithmus mit allen Knoten des Graphen etwas Bestimmtes machen, dann verwendet man die Methode '' | ||
+ | |||
+ | <code java> | ||
+ | import java.util.List; | ||
+ | </ | ||
<code java> | <code java> | ||
Zeile 21: | Zeile 30: | ||
<panel title=" | <panel title=" | ||
Soll der Algorithmus mit bestimmten Knoten/ | Soll der Algorithmus mit bestimmten Knoten/ | ||
+ | |||
+ | <code java> | ||
+ | import java.util.List; | ||
+ | </ | ||
+ | |||
<code java> | <code java> | ||
Zeile 42: | Zeile 56: | ||
+ | </ | ||
+ | <panel title=" | ||
+ | Möchte man eine Knoten- oder Kantenliste sortieren oder den größten/ | ||
+ | Zunächst holt man sich eine Liste der Knoten/ | ||
+ | |||
+ | <code java> | ||
+ | import java.util.List; | ||
+ | import java.util.Collections; | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | // Liste aller Kanten holen | ||
+ | List< | ||
+ | // Kanten nach Gewicht aufsteigend sortieren | ||
+ | Collections.sort(kanten); | ||
+ | // Kante mit minimalem bzw. maximalem Gewicht ermitteln | ||
+ | Kante min = kanten.get(0); | ||
+ | Kante max = kanten.get(kanten.size()-1); | ||
+ | </ | ||
+ | |||
+ | 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=" | ||
+ | In vielen Fällen arbeitet man die Knoten in einer vorher nicht feststehenden Reihenfolge ab. Die Knoten werden während des Algorithmus einer ToDo-Liste hinzugefügt und dann der Reihe nach abgearbeitet, | ||
+ | |||
+ | <code java> | ||
+ | import java.util.ArrayList; | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | // ToDo-Liste erzeugen und mit Startknoten füllen | ||
+ | ArrayList< | ||
+ | toDo.add(getStartKnoten()); | ||
+ | |||
+ | // Solange die ToDo-Liste nicht leer ist... | ||
+ | while(toDo.size()> | ||
+ | // ersten Knoten aus der Liste herausnehmen | ||
+ | Knoten k = toDo.remove(0); | ||
+ | |||
+ | // markiere ihn als besucht | ||
+ | k.setBesucht(true); | ||
+ | |||
+ | // füge alle nicht besuchten Nachbarknoten der Liste hinzu | ||
+ | for(Knoten nachbar : g.getNachbarknoten(k)) { | ||
+ | if(!nachbar.isMarkiert() && !toDo.contains(nachbar)) { | ||
+ | toDo.add(0, n); //füge am Anfang der Liste hinzu | ||
+ | // oder | ||
+ | // toDo.add(n) | ||
+ | } | ||
+ | } | ||
+ | step(); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | 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(" | ||
+ | </ | ||
+ | |||
+ | {{: | ||
</ | </ | ||
</ | </ |