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

Graphenalgorithmen: Einführung

Einführung in die Darstellung und grundlegende Traversierung von Graphen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Modellieren
• KMK: Sekundarstufe II - Algorithmen entwerfen

Über dieses Thema

Graphenalgorithmen: Einführung führt Schüler in die Darstellung und Traversierung von Graphen ein. Sie lernen, reale Probleme wie soziale Netzwerke oder Navigationssysteme mit Knoten und Kanten zu modellieren. Graphen werden als Adjazenzlisten oder -matrizen dargestellt, was die Implementierung von Algorithmen erleichtert. Breitensuche (BFS) erkundet schichtweise alle benachbarten Knoten, während Tiefensuche (DFS) tiefe Pfade priorisiert. Der Vergleich beider Verfahren zeigt, wie die Wahl des Algorithmus vom Problem abhängt, etwa BFS für kürzeste Wege in ungewichteten Graphen.

Diese Inhalte knüpfen an KMK-Standards für Sekundarstufe II an: Modellieren realer Probleme und Entwurf von Algorithmen. Schüler analysieren, warum Graphen in Alltagsanwendungen zentral sind, wie Freundschaften in Netzwerken oder Routenplanung. Sie üben, Traversierungen manuell nachzuvollziehen und pseudocode zu schreiben, um Komplexität zu verstehen.

Aktive Lernmethoden eignen sich hervorragend, weil Schüler Graphen physisch bauen und Algorithmen mit Objekten simulieren können. Solche hands-on-Aktivitäten machen abstrakte Strukturen konkret, fördern Diskussionen über Unterschiede von BFS und DFS und stärken das algorithmische Denken nachhaltig.

Leitfragen

1. Wie lassen sich reale Probleme mithilfe von Graphen modellieren?
2. Vergleichen Sie Breitensuche (BFS) und Tiefensuche (DFS) bei der Traversierung von Graphen.
3. Analysieren Sie die Bedeutung von Graphen in sozialen Netzwerken und Navigationssystemen.

Lernziele

• Modellieren Sie reale Probleme, wie z.B. soziale Netzwerke oder Routenplanung, mithilfe von Graphen (Knoten und Kanten).
• Vergleichen Sie die Funktionsweise und Anwendungsbereiche der Breitensuche (BFS) und Tiefensuche (DFS) zur Traversierung von Graphen.
• Analysieren Sie die Effizienz von BFS und DFS für verschiedene Aufgabenstellungen, z.B. das Finden des kürzesten Weges in einem ungewichteten Graphen.
• Demonstrieren Sie die Darstellung von Graphen mittels Adjazenzlisten und Adjazenzmatrizen in Pseudocode.
• Erklären Sie die Bedeutung von Graphen für die Struktur und Analyse von sozialen Netzwerken und Navigationssystemen.

Bevor es losgeht

Grundlagen der Programmierung: Datenstrukturen

Warum: Schüler müssen grundlegende Konzepte von Datenstrukturen wie Listen und Arrays kennen, um Adjazenzlisten und -matrizen zu verstehen.

Grundlagen der Programmierung: Kontrollstrukturen

Warum: Das Verständnis von Schleifen (for, while) und bedingten Anweisungen (if-else) ist essenziell für die Implementierung von Graphenalgorithmen.

Schlüsselvokabular

Graph	Eine Datenstruktur, die aus einer Menge von Knoten (Eckpunkten) und einer Menge von Kanten besteht, die Paare von Knoten verbinden.
Knoten (Vertex)	Ein Element in einem Graphen, das oft als Punkt oder Kreis dargestellt wird. Repräsentiert Objekte oder Entitäten.
Kante (Edge)	Eine Verbindung zwischen zwei Knoten in einem Graphen, oft als Linie dargestellt. Repräsentiert Beziehungen oder Verbindungen.
Breitensuche (BFS)	Ein Algorithmus zur Traversierung von Graphen, der schichtweise alle erreichbaren Knoten von einem Startknoten aus erkundet.
Tiefensuche (DFS)	Ein Algorithmus zur Traversierung von Graphen, der versucht, so tief wie möglich entlang jedes Zweiges zu gehen, bevor er zurückkehrt.
Adjazenzliste	Eine Methode zur Darstellung eines Graphen, bei der für jeden Knoten eine Liste der benachbarten Knoten gespeichert wird.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Graphen sind immer gerichtet und ohne Zyklen.

Was Sie stattdessen lehren sollten

Graphen können ungerichtet sein und Zyklen enthalten, was Traversierungen kompliziert. Aktive Modellierungen mit physischen Objekten helfen Schülern, Zyklen zu entdecken und Unterschiede zu ungerichteten Graphen zu sehen.

Häufige Fehlvorstellung

BFS und DFS liefern immer denselben Traversierungsreihenfolge.

Was Sie stattdessen lehren sollten

Die Reihenfolge hängt von der Startposition und Nachbarschaftsreihenfolge ab. Peer-Simulationen mit Murmeln zeigen Variationen und fördern Verständnis durch wiederholtes Ausführen.

Häufige Fehlvorstellung

Adjazenzmatrizen sind immer effizienter als Listen.

Was Sie stattdessen lehren sollten

Matrizen verbrauchen mehr Speicher bei großen Graphen. Vergleichsaufgaben in Gruppen verdeutlichen Vor- und Nachteile durch praktische Berechnungen.

Ideen für aktives Lernen

Gruppenmodellierung: Städtenetzwerk bauen

Schüler erhalten Kartenkarten als Knoten und Fäden als Kanten, um ein Städtenetzwerk zu modellieren. Sie markieren Startknoten und traversieren mit BFS und DFS, notieren besuchte Knoten. Abschließend diskutieren sie Anwendungen in Navigationssystemen.

45 Min.·Kleingruppen

Planspiel: Murmel-Traversierung

Verwenden Sie einen Graphen aus Pappkarton mit Löchern als Knoten. Murmeln rollen für BFS (alle Nachbarn zuerst) oder DFS (tief zuerst). Gruppen protokollieren Pfade und vergleichen Ergebnisse.

30 Min.·Partnerarbeit

Programmierpraxis: Einfache Traversierung

Schüler implementieren BFS und DFS in Python mit einer Adjazenzliste. Testen Sie mit einem sozialen Netzwerk-Beispiel. Paare debuggen gegenseitig und visualisieren Pfade mit Matplotlib.

50 Min.·Partnerarbeit

Fishbowl-Diskussion: Reale Modelle analysieren

Präsentieren Sie Graphen aus Facebook oder Google Maps. Whole class diskutiert Modellierung, traversiert manuell und bewertet BFS/DFS-Eignung.

35 Min.·Ganze Klasse

Bezüge zur Lebenswelt

• Google Maps oder andere Navigationsdienste nutzen Graphenalgorithmen, um die schnellste oder kürzeste Route zwischen zwei Orten zu berechnen. Die Straßen und Kreuzungen werden als Knoten und Kanten modelliert.
• Soziale Netzwerke wie Facebook oder LinkedIn stellen Freundschaftsbeziehungen als Graphen dar. Algorithmen wie BFS und DFS können verwendet werden, um Gemeinsamkeiten zwischen Nutzern zu finden oder die Reichweite von Informationen zu analysieren.
• In der Logistik werden Lieferketten und Transportrouten oft als Graphen modelliert, um effiziente Planungen zu ermöglichen. Unternehmen wie DHL oder Amazon setzen solche Modelle zur Optimierung ihrer Abläufe ein.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler ein Blatt mit einem kleinen, ungerichteten Graphen (z.B. 5 Knoten, 6 Kanten). Bitten Sie die Schüler, eine Adjazenzliste für diesen Graphen zu erstellen und die Reihenfolge der besuchten Knoten bei einer manuellen Tiefensuche (DFS) ausgehend von einem bestimmten Knoten anzugeben.

Diskussionsfrage

Stellen Sie die Frage: 'Unter welchen Umständen wäre die Breitensuche (BFS) besser geeignet als die Tiefensuche (DFS), um Informationen in einem großen sozialen Netzwerk zu verbreiten? Begründen Sie Ihre Antwort anhand der Funktionsweise beider Algorithmen.'

Kurze Überprüfung

Zeigen Sie eine einfache Adjazenzmatrix und fragen Sie: 'Welche Knoten sind direkt miteinander verbunden? Geben Sie die Knotenpaare an.' Wiederholen Sie dies für eine Adjazenzliste.

Häufig gestellte Fragen

Wie modellieren Schüler reale Probleme mit Graphen?

Schüler übersetzen Szenarien wie Freundschaften in sozialen Netzwerken oder Straßennetze in Knoten und Kanten. Sie wählen Darstellungen wie Adjazenzlisten für sparse Graphen und testen Traversierungen. Dies trainiert Modellierfähigkeiten nach KMK-Standards und verbindet Theorie mit Praxis in 11. Klasse.

Was ist der Unterschied zwischen BFS und DFS?

BFS traversiert schichtweise und findet kürzeste Wege in ungewichteten Graphen, DFS geht tief in einen Pfad. Schüler vergleichen durch manuelle Simulationen, wann welcher Algorithmus optimal ist, etwa BFS für Netzwerkabstände oder DFS für Pfadfindung in Labyrinthen.

Wie kann aktives Lernen Graphenalgorithmen verständlicher machen?

Hands-on-Aktivitäten wie Graphen bauen mit Karten oder Murmel-Simulationen machen Traversierungen sichtbar. Schüler führen BFS und DFS selbst aus, diskutieren Ergebnisse in Gruppen und entdecken Unterschiede intuitiv. Dies stärkt Verständnis, reduziert Abstraktheit und fördert algorithmisches Denken langfristig.

Warum sind Graphen in Navigationssystemen wichtig?

Graphen modellieren Kreuzungen als Knoten und Straßen als Kanten. BFS berechnet effiziente Routen. Schüler analysieren Beispiele wie Google Maps, implementieren einfache Versionen und verstehen Komplexitätsskala in realen Anwendungen.