Graphenalgorithmen: Traversierung (BFS/DFS)

Aktive Lernformen eignen sich besonders für Graphenalgorithmen, weil Schülerinnen und Schüler durch eigenes Implementieren und Testen ein tiefes Verständnis für die Unterschiede zwischen BFS und DFS entwickeln. Die Visualisierung der Traversierungen hilft, abstrakte Konzepte wie Warteschlangen und Stapel durch konkrete Erfahrungen greifbar zu machen.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 4 Aktivitäten
• 20 Min.–50 Min.

Lernziele

1. Vergleichen Sie die Effizienz von Breitensuche (BFS) und Tiefensuche (DFS) bei der Lösung von Labyrinthproblemen unterschiedlicher Komplexität.
2. Analysieren Sie die Zeit- und Platzkomplexität von BFS und DFS für verschiedene Graphendarstellungen (Adjazenzliste, Adjazenzmatrix).
3. Entwerfen Sie einen modifizierten DFS-Algorithmus zur Erkennung von Zyklen in einem gerichteten Graphen.
4. Demonstrieren Sie die Anwendung von BFS zur Ermittlung der kürzesten Pfade in einem ungewichteten Netzwerk.

Problemorientiertes Lernen

⏱ 30 Min.·Partnerarbeit

Paarprogrammierung: BFS-Implementierung

Paare coden BFS in Python auf einem vorgegebenen Graphen und messen besuchte Knoten. Sie testen mit verschiedenen Startknoten und protokollieren Pfade. Abschließend diskutieren sie kürzeste Distanzen.

Vorbereitung & Details

Vergleichen Sie die Anwendungsbereiche von BFS und DFS in realen Szenarien.

Moderationstipp: Während der Paarprogrammierung für BFS sollte ein Partner den Code schreiben, der andere die Debugging-Aufgaben übernehmen, um kognitive Last zu teilen und Reflexion zu fördern.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 45 Min.·Kleingruppen

Small Groups: DFS-Zykel-Erkennung

Gruppen implementieren DFS zur Zykel-Detektion in gerichteten Graphen. Sie erzeugen Testgraphen mit Zyklen und ohne, laufen den Algorithmus und validieren Ergebnisse. Eine Präsentation der Komplexität schließt ab.

Vorbereitung & Details

Designen Sie einen Algorithmus zur Erkennung von Zyklen in einem Graphen.

Moderationstipp: Bei der DFS-Zykel-Erkennung in Kleingruppen geben Sie den Lernenden farbige Stifte, um besuchte Knoten und Back-Edges direkt im Graphen zu markieren – das macht den Algorithmus sichtbar.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 50 Min.·Ganze Klasse

Whole Class: Vergleichs-Rennen

Die Klasse teilt sich in BFS- und DFS-Teams, die Algorithmen auf gemeinsamen Graphen anwenden. Ergebnisse werden live visualisiert und diskutiert. Alle analysieren Vor- und Nachteile.

Vorbereitung & Details

Analysieren Sie die Zeit- und Platzkomplexität von BFS und DFS.

Moderationstipp: Beim Vergleichs-Rennen lassen Sie die Lernenden die Traversierungen im Plenum live an der Tafel simulieren, um Unsicherheiten in Echtzeit zu klären und präzise Fragen zu stellen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 20 Min.·Einzelarbeit

Individual: Komplexitäts-Analyse

Jede Schülerin oder jeder Schüler simuliert BFS/DFS auf wachsenden Graphen und zeichnet Zeitverläufe auf. Sie vergleichen mit O(V+E) und berichten Abweichungen.

Vorbereitung & Details

Vergleichen Sie die Anwendungsbereiche von BFS und DFS in realen Szenarien.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit einer anschaulichen Einführung, indem sie die Algorithmen mit einfachen Beispielen wie einem Familienbaum erklären. Sie vermeiden abstrakte Definitionen zu Beginn und setzen stattdessen auf handlungsorientierte Erkundung. Wichtig ist, dass Lehrkräfte gezielt Fehler analysieren lassen, etwa warum DFS in einem zyklischen Graphen nicht terminiert, um nachhaltiges Verständnis zu schaffen.

Was Sie erwartet

Erfolgreiche Lernende können BFS und DFS selbstständig implementieren, die Algorithmen auf Graphen anwenden und die Ergebnisse der Traversierungen korrekt einordnen. Sie erkennen, wann welcher Algorithmus sinnvoll ist und können die Eigenschaften wie Speicherbedarf oder Pfadfindung begründen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Paarprogrammierung zur BFS-Implementierung, achten Sie darauf, dass einige Schüler annehmen, BFS finde in allen Graphen den kürzesten Pfad.

Was Sie stattdessen lehren sollten

Fügen Sie einen gewichteten Graphen als Testfall in die Aufgabenstellung ein und bitten Sie die Lernenden, die Pfadlängen manuell zu berechnen, um den Unterschied zu Dijkstra direkt zu erkennen.

Häufige Fehlvorstellung

Während der Kleingruppenarbeit zur DFS-Zykel-Erkennung, beobachten Sie, dass einige Schüler glauben, DFS sei immer speichereffizienter als BFS.

Was Sie stattdessen lehren sollten

Geben Sie den Gruppen große Graphen (z. B. 100 Knoten in einer Linie), bei denen DFS zu einem Stack-Overflow führt, während BFS stabil bleibt – das macht den Vorteil der Warteschlange sichtbar.

Häufige Fehlvorstellung

Während des Vergleichs-Rennens im Plenum, merken Sie, dass Lernende die Anwendungsbereiche von BFS und DFS vermischen.

Was Sie stattdessen lehren sollten

Lassen Sie die Gruppen vor dem Rennen konkrete Szenarien wie Flood-Fill oder Topologie-Sortierung diskutieren und mit ihren Algorithmen testen, um die Unterschiede zu verankern.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Paarprogrammierung zur BFS-Implementierung geben Sie den Lernenden einen kleinen, ungerichteten Graphen (z. B. 5 Knoten, 6 Kanten) und bitten Sie sie, die Reihenfolge der besuchten Knoten für BFS (startend bei Knoten A) und DFS (startend bei Knoten A) aufzuschreiben. Vergleichen Sie die Ergebnisse im Plenum.

Lernstandskontrolle

Nach dem Vergleichs-Rennen stellen Sie den Lernenden zwei Szenarien vor: 1. Ein soziales Netzwerk, das nach Freunden von Freunden sucht. 2. Ein Roboter, der einen Weg durch ein unbekanntes Labyrinth findet. Bitten Sie sie zu entscheiden, welcher Algorithmus (BFS oder DFS) besser geeignet ist und begründen Sie ihre Wahl kurz.

Diskussionsfrage

Nach der Kleingruppenarbeit zur DFS-Zykel-Erkennung diskutieren Sie mit den Lernenden: 'Unter welchen Bedingungen ist die Adjazenzliste einer Adjazenzmatrix für die Implementierung von BFS und DFS überlegen, und wann ist es umgekehrt? Betrachten Sie dabei sowohl die Zeit- als auch die Platzkomplexität für dünn besetzte und dicht besetzte Graphen.'

Erweiterungen & Unterstützung

• Fordern Sie Schülerinnen und Schüler auf, den Dijkstra-Algorithmus mit einer Prioritätswarteschlange zu implementieren und mit BFS in gewichteten Graphen zu vergleichen.
• Für Lernende mit Schwierigkeiten: Geben Sie ihnen einen vorbereiteten Graphen mit markierten Startknoten und leeren Tabellen für BFS und DFS, um die Traversierungsreihenfolge Schritt für Schritt zu notieren.
• Vertiefen Sie die Thematik mit einer Simulation, in der die Lernenden einen Roboter steuern, der ein Labyrinth sowohl mit BFS als auch DFS durchquert und die Effizienz vergleicht.

Schlüsselvokabular

Breitensuche (BFS)	Ein Graph-Traversierungsalgorithmus, der alle Knoten auf der aktuellen Ebene erkundet, bevor er zur nächsten Ebene übergeht. Er verwendet typischerweise eine Warteschlange (Queue).
Tiefensuche (DFS)	Ein Graph-Traversierungsalgorithmus, der so weit wie möglich entlang jedes Zweigs geht, bevor er zurückgeht. Er verwendet typischerweise Rekursion oder einen Stapel (Stack).
Zykluserkennung	Der Prozess der Identifizierung von Pfaden in einem Graphen, die an ihrem Ausgangsknoten enden. Dies ist für die Analyse gerichteter und ungerichteter Graphen relevant.
Adjazenzliste	Eine Methode zur Darstellung eines Graphen, bei der für jeden Knoten eine Liste der direkt verbundenen Nachbarknoten gespeichert wird.
Adjazenzmatrix	Eine Methode zur Darstellung eines Graphen als quadratische Matrix, wobei ein Eintrag angibt, ob eine Kante zwischen zwei Knoten existiert.