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:kuerzeste_pfade:traversierungen:start [11.09.2024 15:28] – [Implementation] Marco Kuemmel | faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start [12.09.2024 08:53] (aktuell) – Marco Kuemmel | ||
|---|---|---|---|
| Zeile 30: | Zeile 30: | ||
| < | < | ||
| // 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 | + | wenn w nicht 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: | ||
| < | < | ||
| // 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 | + | wenn w nicht 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 Algorithmus. Färbe die besuchten Knoten ein und nummeriere sie, sodass du den Ablauf nachvollziehen kannst. Teste deine Algorithmen mit dem Beispielgraphen '' | + | Implementiere Breiten- und Tiefensuche im Graphentester in einem eigenen Algorithmus. |
| 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: | ||