Informatik · Klasse 13 · Datenstrukturen und Algorithmen-Analyse · 1. Halbjahr

Graphenalgorithmen: Traversierung (BFS/DFS)

Die Schülerinnen und Schüler implementieren und vergleichen Breitensuche (BFS) und Tiefensuche (DFS).

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

Über dieses Thema

Graphenalgorithmen zur Traversierung, insbesondere Breitensuche (BFS) und Tiefensuche (DFS), bilden einen Kernbereich der Informatik in der Oberstufe. Schülerinnen und Schüler implementieren BFS mit einer Queue, um kürzeste Pfade in ungewogenen Graphen zu finden, und DFS mit Rekursion oder Stack, um tiefe Erkundungen durchzuführen. Sie vergleichen Eigenschaften, etwa die Level-by-Level-Verarbeitung bei BFS gegenüber der Pfadpriorierung bei DFS, und analysieren reale Szenarien wie Netzwerkrouting oder Labyrinthlösung.

Die KMK-Standards zu Algorithmen und Strukturieren werden adressiert, indem Lernende Zeit- und Platzkomplexität O(V+E) berechnen und Zyklen erkennen. Dies fördert algorithmisches Denken und verbindet Theorie mit Praxis, z. B. durch Design eigener Algorithmen für Graphenprobleme.

Aktives Lernen ist hier besonders wirksam, weil Schüler Graphen selbst bauen, Algorithmen coden und Ergebnisse visualisieren. Solche hands-on-Aktivitäten machen Komplexitäten erlebbar, regen Debugging an und vertiefen das Verständnis durch direkte Vergleiche von BFS und DFS in interaktiven Szenarien.

Leitfragen

1. Vergleichen Sie die Anwendungsbereiche von BFS und DFS in realen Szenarien.
2. Designen Sie einen Algorithmus zur Erkennung von Zyklen in einem Graphen.
3. Analysieren Sie die Zeit- und Platzkomplexität von BFS und DFS.

Lernziele

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

Bevor es losgeht

Grundlagen von Graphen

Warum: Die Schüler müssen die Konzepte von Knoten, Kanten, gerichteten und ungerichteten Graphen verstehen, um Traversierungsalgorithmen anwenden zu können.

Grundlegende Datenstrukturen: Listen und Stacks/Queues

Warum: Die Implementierung von BFS und DFS basiert direkt auf der Verwendung von Warteschlangen und Stacks, deren Funktionsweise bekannt sein muss.

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.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

BFS findet immer den kürzesten Pfad, unabhängig vom Graphentyp.

Was Sie stattdessen lehren sollten

BFS garantiert kürzeste Pfade nur in ungewogenen Graphen; bei Gewichten versagt es. Aktive Simulationen mit gewichteten Graphen helfen, wo Schüler Pfade manuell nachvollziehen und den Unterschied zu Dijkstra entdecken.

Häufige Fehlvorstellung

DFS ist immer effizienter als BFS bei Speicher.

Was Sie stattdessen lehren sollten

DFS spart Stapelspeicher bei Rekursion, kann aber bei tiefen Graphen stack overflowen. Gruppenexperimente mit großen Graphen zeigen, wie Queues bei BFS stabiler wirken und aktives Debugging Klarheit schafft.

Häufige Fehlvorstellung

Beide Algorithmen haben identische Anwendungen.

Was Sie stattdessen lehren sollten

BFS eignet sich für Breitenprobleme wie Flood-Fill, DFS für Topologie-Sortierung. Vergleichsaufgaben in Teams verdeutlichen reale Unterschiede durch praktische Tests.

Ideen für aktives Lernen

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.

30 Min.·Partnerarbeit

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.

45 Min.·Kleingruppen

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.

50 Min.·Ganze Klasse

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.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Netzwerkadministratoren nutzen BFS, um die schnellsten Routen für Datenpakete in Computernetzwerken zu finden, ähnlich wie Google Maps Routen berechnet.
• Softwareentwickler verwenden DFS, um Abhängigkeiten in Build-Systemen zu analysieren oder um Pfade in Dateisystemen zu durchsuchen, beispielsweise bei der Implementierung von 'Finden'-Funktionen.
• Biologen könnten DFS anwenden, um Stammbäume zu analysieren und Verwandtschaftsverhältnisse zu verfolgen, indem sie die Verzweigungsstruktur der Abstammung erkunden.

Ideen zur Lernstandserhebung

Kurze Überprüfung

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

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

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

Häufig gestellte Fragen

Wie unterscheiden sich BFS und DFS in der Praxis?

BFS erkundet Graphen schichtweise mit einer Queue und findet kürzeste Pfade in ungewogenen Graphen, ideal für Netzwerke. DFS taucht tief mit Rekursion ein, eignet sich für Zykelprüfung oder Pfadfindung in Spielen. Schüler vergleichen sie durch Implementierung: BFS verarbeitet alle Nachbarn zuerst, DFS priorisiert einen Pfad vollständig. Dies schult analytisches Denken für reale Algorithmenwahl.

Wie erkennt man Zyklen mit DFS?

DFS markiert besuchte Knoten und prüft Rückkanten zu Ahnen. Bei Rekursion speichert es den Pfad und erkennt Zyklen durch Wiederholungen. Schüler implementieren dies schrittweise: Starte bei einem Knoten, markiere als besucht, rekuriere zu Nachbarn. Aktive Codierung mit Visualisierern wie Graphviz macht den Prozess nachvollziehbar und festigt Komplexitätsverständnis.

Wie fördert aktives Lernen das Verständnis von BFS und DFS?

Aktives Lernen lässt Schüler Graphen zeichnen, Algorithmen coden und ausführen, was abstrakte Traversierungen konkret macht. Paar- oder Gruppenarbeit mit Wettbewerben vergleicht Laufzeiten live, Debugging schult Fehlersuche. Solche Methoden verbinden Theorie mit Praxis, verbessern Retention und motivieren durch sichtbare Erfolge, wie kürzeste Pfade in eigenen Szenarien.

Was ist die Komplexität von BFS und DFS?

Beide Algorithmen haben Zeitkomplexität O(V+E) und Platzkomplexität O(V) durch Queue oder Stack. BFS braucht mehr Speicher für Breiten, DFS weniger bei flachen Graphen. Schüler analysieren dies durch Simulationen großer Graphen: Zählen Besuche und vergleichen mit Big-O. Praktische Tests bestätigen Theorie und bereiten auf fortgeschrittene Analysen vor.