faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start [21.11.2022 16:46] – [Implementation] Frank Schiebelfaecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start [12.09.2024 08:53] (aktuell) – Marco Kuemmel
Zeile 10: Zeile 10:
 der zunehmenden Entfernung vom Startknoten.  der zunehmenden Entfernung vom Startknoten. 
  
-Ebene 0 enthält den Startknoten s, sonst nichts. Ebene 1 ist die Menge der Knoten, die eine Kante von s entfernt sind, also die Nachbarn von s. Diese Knoten werden bei der Breitensuche direkt im Anschluss des Startknotens untersucht, die Bachbarknoten dieser Knoten werden zur Untersuchung in Ebene 3 vorgemerkt.+Ebene 0 enthält den Startknoten s, sonst nichts. Ebene 1 ist die Menge der Knoten, die eine Kante von s entfernt sind, also die Nachbarn von s. Diese Knoten werden bei der Breitensuche direkt im Anschluss des Startknotens untersucht, die Nachbarknoten dieser Knoten werden zur Untersuchung in Ebene 2 vorgemerkt.
  
  
Zeile 25: Zeile 25:
 ==== Implementation ==== ==== Implementation ====
  
-Implementiert wird die Breitensuche mit Hilfe eines [[ faecher:informatik:oberstufe:adt:queue:start|Queues]] für die unbearbeiteten Knoten. Eine Schlange oder ein Queue ist eine einfach "First-In-First-Out"-Datenstruktur, der Pseudocode für eine Breitensuche sieht folgendermaßen aus:+Implementiert wird die Breitensuche mit Hilfe einer [[ faecher:informatik:oberstufe:adt:queue:start|Queue]] für die unbearbeiteten Knoten. Eine Schlange oder eine Queue ist eine einfach "First-In-First-Out"-Datenstruktur, der Pseudocode für eine Breitensuche sieht folgendermaßen aus:
  
  
 <code> <code>
 // Breitensuche // Breitensuche
-markiere den Startknoten s als besucht, alle anderen Knoten als nicht besucht+markiere den Startknoten s als markiert, alle anderen Knoten als nicht markiert
 Q := Ist eine Schlange, die mit dem Startknoten s initialisisert wird Q := Ist eine Schlange, die mit dem Startknoten s initialisisert wird
  
Zeile 36: Zeile 36:
   Entferne den ersten Knoten v der Schlange Q   Entferne den ersten Knoten v der Schlange Q
   für alle Nachbarn w von v:   für alle Nachbarn w von v:
-    wenn w nicht besucht ist: +    wenn w nicht markiert ist: 
-      markiere w als besucht+      setze w als markiert
       füge w ans Ende der Schlange Q an       füge w ans Ende der Schlange Q an
     ende_wenn     ende_wenn
Zeile 55: Zeile 55:
 sondern es werden ausgehend vom aktuellen Knoten immer zuerst die gefundenen Nachbarknoten besucht. Realisiert wird das in der iterativen Variante des Algorithmus durch einen [[faecher:informatik:oberstufe:adt:stack:start|Stack]] für die zu besuchenden Knoten. sondern es werden ausgehend vom aktuellen Knoten immer zuerst die gefundenen Nachbarknoten besucht. Realisiert wird das in der iterativen Variante des Algorithmus durch einen [[faecher:informatik:oberstufe:adt:stack:start|Stack]] für die zu besuchenden Knoten.
  
 +==== Implementation ====
  
 <code> <code>
 // Breitensuche // Breitensuche
-markiere den Startknoten s als besucht, alle anderen Knoten als nicht besucht+markiere den Startknoten s als markiert, alle anderen Knoten als nicht markiert
 S := Ist ein Stapel, der mit dem Startknoten s initialisisert wird S := Ist ein Stapel, der mit dem Startknoten s initialisisert wird
  
Zeile 64: Zeile 65:
   Entferne den obersten Knoten v vom Stack S   Entferne den obersten Knoten v vom Stack S
   für alle Nachbarn w von v:   für alle Nachbarn w von v:
-    wenn w nicht besucht ist: +    wenn w nicht markiert ist: 
-      markiere w als besucht+      setze w als markiert
       lege w auf dem Stack S ab       lege w auf dem Stack S ab
     ende_wenn     ende_wenn
Zeile 76: Zeile 77:
 {{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:dfs.drawio.png?600 |}} {{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:dfs.drawio.png?600 |}}
  
 +Man kann gut erkennen, dass der Graph zunächst in der "Tiefe" bis zum Knoten **e** durchlaufen wird, bevor es beim Nachbarn **b** des Startknotens weitergeht.
 +
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A1) Implementation ===
 +
 +
 +
 +Implementiere Breiten- und Tiefensuche im Graphentester in einem eigenen Algorithmus. **Färbe** die besuchten Knoten ein und **nummeriere** sie, sodass du den Ablauf nachvollziehen kannst. Teste deine Algorithmen mit dem Beispielgraphen ''03_routenplanung/00_traversierung''.
 +
 +Für den Queue kannst du z.B. das Queue-Interface mit einer Linked-List verwenden:
 +
 +<code java>
 +import java.util.LinkedList;
 +import java.util.Queue;
 +
 +Queue<Knoten> q = new LinkedList<>();
 +q.add(s);  // Fügt den Knoten der Queue am Ende hinzu s, muss ein Knoten sein
 +Knoten aktuell = q.remove(); // Entfernt den vordersten Knoten aus der Queue
 +Knoten vorne = q.peek();  // Gibt den vordersten Knoten zurück, ohne ihn zu entfernen
 +int size = q.size() // Gibt die Zahl der Elemente in der Schlange zurück
 +// q.isEmpty() ist wahr, wenn die Schlange leer ist.
 +</code>
 +
 +Für den Stack kannst du die Klasse Stack verwenden:
 +
 +<code java>
 +import java.util.Stack
 +
 +Stack<Knoten> st = new Stack<>();
 +st.push(k) // Legt den Knoten k auf den Stapel
 +Knoten aktuell = st.pop() // Hebt den obersten Knoten ab
 +st.isEmpty() // ist wahr, wenn der Stapel leer ist
 +</code>
  
 +<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
  
  
  • faecher/informatik/oberstufe/graphen/zpg/kuerzeste_pfade/traversierungen/start.1669049169.txt.gz
  • Zuletzt geändert: 21.11.2022 16:46
  • von Frank Schiebel