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 17:35] – [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 59: Zeile 59:
 <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 65: 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 84: Zeile 84:
 === (A1) Implementation === === (A1) Implementation ===
  
-Implementiere Breiten- und Tiefensuche im Graphentester in einem Eigenen Algorithnmus. Färbe die besuchten Knoten ein und nummeriere sie, so dass du den Ablauf nachvollziehen kannst. Teste deine Algorithmen mit dem Beispielgraphen ''03_routenplanung/00_traversierung''.+ 
 + 
 +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: Für den Queue kannst du z.B. das Queue-Interface mit einer Linked-List verwenden:
Zeile 110: Zeile 112:
 st.isEmpty() // ist wahr, wenn der Stapel leer ist st.isEmpty() // ist wahr, wenn der Stapel leer ist
 </code> </code>
 +
 +<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
  
  
  • faecher/informatik/oberstufe/graphen/zpg/kuerzeste_pfade/traversierungen/start.1669052118.txt.gz
  • Zuletzt geändert: 21.11.2022 17:35
  • von Frank Schiebel