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:04] – [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 35: 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 43: Zeile 44:
 </code> </code>
  
-Die folgende Grafik zeigt den Ablauf am Beispielgraphen von oben. Rechts ist jeweils der Zustand des Queues dargestellt. +Die folgende Grafik zeigt den Ablauf am Beispielgraphen von oben. Rechts ist jeweils der Zustand des Queues dargestellt, gestrichelt ist dargestellt, wie sich die "Ebenengrenze" verschiebt. Neue Knoten werden links in den Queue eingestellt und rechts entnommen/gelöscht. 
 + 
 +{{  :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:bfs.drawio.png?400  |}} 
 + 
 + 
 +===== Tiefensuche ===== 
 + 
 + 
 +Bei der **Tiefensuche** werden die Knoten des Graphen nicht wie bei der Breitensuche "vorsichtig" Ebene für Ebene besucht,  
 +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> 
 +// Breitensuche 
 +markiere den Startknoten s als markiert, alle anderen Knoten als nicht markiert 
 +S := Ist ein Stapel, der mit dem Startknoten s initialisisert wird 
 + 
 +solange "S ist nicht leer": 
 +  Entferne den obersten Knoten v vom Stack S 
 +  für alle Nachbarn w von v: 
 +    wenn w nicht markiert ist: 
 +      setze w als markiert 
 +      lege w auf dem Stack S ab 
 +    ende_wenn 
 +  ende_für 
 +ende_solange 
 +</code> 
 + 
 +Die folgende Abbildung zeigt den Ablauf: 
 + 
 +{{ :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.1669046686.txt.gz
  • Zuletzt geändert: 21.11.2022 16:04
  • von Frank Schiebel