Informatik · Klasse 10 · Algorithmen und Komplexität · 2. Halbjahr

Suchen in Graphen und Bäumen

Die Schülerinnen und Schüler navigieren in komplexen Datenstrukturen wie sozialen Netzen oder Karten.

• KMK Bildungsstandards
• KMK: STD.01
• KMK: STD.16

Über dieses Thema

Das Thema 'Suchen in Graphen und Bäumen' führt Schülerinnen und Schüler in die Navigation komplexer Datenstrukturen ein, wie sie in sozialen Netzwerken oder Kartennetzen vorkommen. Sie modellieren Graphen als Knoten und Kanten, um Wege zu berechnen, und Bäume als hierarchische Strukturen für effiziente Suchen. Praktische Beispiele wie das Navigationssystem von Berlin nach München verdeutlichen Algorithmen: Die Breitensuche (BFS) findet den kürzesten Pfad in ungewichteten Graphen, während die Tiefensuche (DFS) tiefe Erkundungen priorisiert. Schüler vergleichen diese Methoden und analysieren ihre Komplexität.

Im KMK-Standard STD.01 und STD.16 zu Algorithmen und Komplexität verbindet das Thema Theorie mit Praxis. Es schult systemisches Denken, indem Hierarchien in Informatik abgebildet werden, und bereitet auf reale Anwendungen wie Suchmaschinen oder Dateisysteme vor. Schüler erkennen, wie Datenstrukturen Alltagsprobleme lösen.

Aktives Lernen eignet sich hervorragend, da abstrakte Algorithmen durch handfeste Modelle und Simulationen greifbar werden. Wenn Gruppen Graphen mit Kartenpins bauen oder Suchalgorithmen schrittweise ausführen, festigen sie Konzepte durch Beobachtung und Diskussion. Das macht Fehler sichtbar und fördert tiefes Verständnis.

Leitfragen

1. Wie findet ein Navi den kürzesten Weg von Berlin nach München?
2. Was unterscheidet die Tiefensuche von der Breitensuche?
3. Wie werden Hierarchien in der Informatik abgebildet?

Lernziele

• Vergleichen Sie die Effektivität von Breitensuche (BFS) und Tiefensuche (DFS) bei der Pfadfindung in verschiedenen Graphentypen.
• Analysieren Sie die Komplexität von BFS und DFS in Bezug auf Zeit und Speicherbedarf für gegebene Graphen.
• Entwerfen Sie einen Baumdatentyp zur effizienten Speicherung und Suche von hierarchischen Informationen.
• Erklären Sie die Anwendung von Graphen- und Baumstrukturen bei der Routenplanung in Navigationssystemen.
• Identifizieren Sie geeignete Algorithmen (BFS, DFS) für spezifische Suchprobleme in gegebenen Szenarien.

Bevor es losgeht

Grundlagen von Algorithmen und Ablaufsteuerung

Warum: Schüler müssen grundlegende Konzepte wie Schleifen, Bedingungen und die schrittweise Ausführung von Anweisungen verstehen, um Suchalgorithmen nachvollziehen zu können.

Einführung in Datenstrukturen: Listen und Arrays

Warum: Das Verständnis von geordneten Sammlungen von Daten ist eine Grundlage für das Verständnis komplexerer Strukturen wie Graphen und Bäume.

Schlüsselvokabular

Graph	Eine Datenstruktur, die aus Knoten (Vertices) und Kanten (Edges) besteht, welche Verbindungen zwischen den Knoten darstellen.
Baum	Ein spezieller Typ von Graph, der eine hierarchische Struktur mit einem Wurzelknoten und untergeordneten Knoten darstellt, ohne Zyklen.
Breitensuche (BFS)	Ein Algorithmus zur Traversierung von Graphen oder Bäumen, der alle Nachbarn eines Knotens besucht, bevor er zu den Nachbarn der Nachbarn übergeht. Findet den kürzesten Weg in ungewichteten Graphen.
Tiefensuche (DFS)	Ein Algorithmus zur Traversierung von Graphen oder Bäumen, der so weit wie möglich entlang jedes Zweigs vordringt, bevor er zurückgeht (Backtracking).
Knoten (Vertex)	Ein grundlegendes Element in einem Graphen oder Baum, das einen Punkt oder eine Entität repräsentiert.
Kante (Edge)	Eine Verbindung zwischen zwei Knoten in einem Graphen, die eine Beziehung oder einen Pfad darstellt.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Breitensuche findet immer den kürzesten Weg in jedem Graphen.

Was Sie stattdessen lehren sollten

BFS garantiert den kürzesten Pfad nur in ungewichteten Graphen. In gewichteten Netzen wie Straßen mit Distanzen braucht es Dijkstra. Aktive Simulationen mit realen Karten helfen Schülern, Gewichtungen zu testen und den Unterschied durch Messen zu entdecken.

Häufige Fehlvorstellung

Graphen und Bäume sind identisch.

Was Sie stattdessen lehren sollten

Bäume sind gerichtete Graphen ohne Zyklen und mit Hierarchie. Aktive Modellierung mit Pins zeigt Schülern Zyklen in Graphen und lineare Pfade in Bäumen, was durch Gruppenvergleiche das Verständnis vertieft.

Häufige Fehlvorstellung

Tiefensuche ist immer effizienter als Breitensuche.

Was Sie stattdessen lehren sollten

DFS kann in langen Pfaden stecken bleiben, BFS ist breiter. Hands-on-Ausführungen auf Papier machen Schülern die Erkundungsreihenfolge sichtbar und fördern Diskussionen über Anwendungsfälle.

Ideen für aktives Lernen

Lernen an Stationen: Graphen bauen

Schüler bauen mit Papier und Fäden einen Graphen einer Stadt. Sie markieren Knoten als Städte und Kanten als Straßen. In Gruppen führen sie BFS durch, um den kürzesten Weg zu finden, und notieren Schritte.

45 Min.·Kleingruppen

Baum-Suche: Hierarchie simulieren

Erstellen Sie einen Familienbaum als Baumstruktur. Schüler suchen mit DFS nach einem Verwandten auf der tiefsten Ebene. Sie vergleichen Ergebnisse mit BFS und diskutieren Vor- und Nachteile.

30 Min.·Partnerarbeit

Computer-Simulation: Algorithmen programmieren

Mit Scratch oder Python implementieren Schüler BFS in einem einfachen Graphen. Sie testen mit verschiedenen Startpunkten und messen Laufdauer. Gemeinsam optimieren sie den Code.

50 Min.·Partnerarbeit

Ganzer Unterricht: Navi-Challenge

Teilen Sie die Klasse in Teams, die ein Navi-Problem lösen. Jede Gruppe simuliert einen Algorithmus auf einer großen Karte und präsentiert den Pfad. Die Klasse bewertet Effizienz.

60 Min.·Kleingruppen

Bezüge zur Lebenswelt

• Bei Google Maps oder anderen Navigationsdiensten werden Graphen verwendet, um Straßennetze darzustellen. BFS wird oft eingesetzt, um den schnellsten oder kürzesten Weg zwischen zwei Punkten zu berechnen, wobei Faktoren wie Verkehr und Entfernung berücksichtigt werden.
• Soziale Netzwerke wie Facebook oder LinkedIn modellieren Verbindungen zwischen Nutzern als Graphen. DFS kann verwendet werden, um Freundschaftsverbindungen in mehreren Graden zu finden oder um Gemeinsamkeiten zwischen Nutzern zu identifizieren.
• Dateisysteme auf Computern sind oft als Bäume strukturiert, wobei Ordner und Unterordner Hierarchien bilden. Die Suche nach einer bestimmten Datei in diesem Baum kann effizient mit DFS oder BFS erfolgen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einem einfachen Graphen (z.B. 5 Knoten, 6 Kanten). Bitten Sie die Schüler, den Graphen mit BFS und dann mit DFS zu durchlaufen und die Reihenfolge der besuchten Knoten aufzuschreiben. Vergleichen Sie die Ergebnisse.

Kurze Überprüfung

Stellen Sie die Frage: 'Ein Freund möchte den kürzesten Weg durch eine Stadt finden, die wie ein Gitter aufgebaut ist. Welchen Suchalgorithmus würden Sie empfehlen und warum?' Bewerten Sie die Antworten auf die korrekte Anwendung von BFS und die Begründung.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwerfen ein System zur Empfehlung von Freunden in einem sozialen Netzwerk. Welche Datenstruktur (Graph oder Baum) wäre besser geeignet und warum? Welche Suchstrategie (BFS oder DFS) würden Sie für die Empfehlungsfindung nutzen?'

Häufig gestellte Fragen

Wie unterscheidet sich Tiefensuche von Breitensuche?

Tiefensuche (DFS) erkundet einen Pfad bis zum Ende, bevor sie zurückkehrt, ideal für Hierarchien. Breitensuche (BFS) durchläuft Ebenen schrittweise und findet kürzeste Pfade in ungewichteten Graphen. In der Praxis testen Schüler beide in Simulationen, um Komplexität und Ergebnisse zu vergleichen, was zu besserem Algorithmusverständnis führt.

Wie findet ein Navi den kürzesten Weg?

Navis nutzen gewichtete Graphen mit Distanzen als Kantengewichte und Algorithmen wie Dijkstra oder A*. Diese erweitern BFS für Gewichte. Schüler modellieren das mit Karten, berechnen manuell und entdecken, warum Heuristiken wie Luftlinie die Suche beschleunigen.

Wie hilft aktives Lernen beim Verständnis von Graphensuchen?

Aktives Lernen macht Algorithmen erfahrbar: Schüler bauen physische Modelle, führen Suchen schrittweise aus und beobachten Pfade entstehen. Gruppenrotationen und Peer-Diskussionen klären Missverständnisse sofort. Solche Methoden verbinden Theorie mit Haptik, steigern Retention und motivieren durch Erfolge bei realen Problemen.

Wie werden Hierarchien in der Informatik als Bäume abgebildet?

Bäume darstellen Ordnerstrukturen, Organisationscharts oder Entscheidungsbäume ohne Zyklen. Jeder Knoten hat einen Elternknoten außer der Wurzel. Schüler üben Suchen darin, um Effizienz zu sehen, und verknüpfen es mit Dateisystemen oder Webseiten-Menüs.