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 [02.07.2024 09:29] – Frank Schiebelfaecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start [12.09.2024 08:53] (aktuell) – Marco Kuemmel
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 86: Zeile 86:
  
  
-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:
  • faecher/informatik/oberstufe/graphen/zpg/kuerzeste_pfade/traversierungen/start.1719912559.txt.gz
  • Zuletzt geändert: 02.07.2024 09:29
  • von Frank Schiebel