Informatik · Klasse 13

Ideen für aktives Lernen

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.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen
• KMK: Sekundarstufe II - Strukturieren und Vernetzen

• 20–50 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• 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.

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.

Worauf zu achten ist

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.

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

Aktivität 02

• 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.

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.

Worauf zu achten ist

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.

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

Aktivität 03

• 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.

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.

Worauf zu achten ist

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.'

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

Aktivität 04

• 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.

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

Worauf zu achten ist

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.

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

Einige Hinweise zum Unterrichten dieser Einheit

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.

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

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

  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.

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

  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.

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

  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.

---

In dieser Übersicht verwendete Methoden

• Problemorientiertes Lernen