Qualifikationsphase

Q1.5 – Graphen (nur Leistungskurs)

Modelle, Datenstrukturen und Algorithmen für netzartige Probleme

In Q1.5 werden reale Netzwerke als Graph modelliert, in geeigneten Datenstrukturen gespeichert und mit systematischen Algorithmen durchsucht.

Leitidee der Seite: Graphen sind Modelle – und Modelle werden erst durch das Zusammenspiel aus Datenstruktur und Algorithmus rechnerisch nutzbar.

Problem → Warum Graphen?
Von der realen Komplexität zum informatischen Kernmodell

Ein Navigationssystem muss in sehr kurzer Zeit eine sinnvolle Route von Start nach Ziel bestimmen. Eine reale Straßenkarte enthält dafür zu viele Details: Straßennamen, Gebäude, grafische Symbole, Flächen, Farben und zusätzliche Kontextinformationen.

Für die Routenplanung reichen dagegen wenige Kerninformationen: Orte, Verbindungen und Entfernungen. Genau diese Reduktion motiviert ein abstraktes Modell.

Modellbildung (Realwelt → Graph)
Abstraktion als Voraussetzung für algorithmisches Arbeiten

Wir verwenden durchgehend ein kleines Straßennetz mit den Orten A bis F. Die linke Darstellung zeigt noch den Realweltbezug, die rechte den bereits abstrahierten Graphen.

Schematisches Straßennetz mit Orten A bis F als Realweltmodell. — Realweltnahes Straßennetz: viele Details, aber noch keine formale Struktur.

Abstrahierter ungerichteter Graph mit den Knoten A bis F. — Abstraktion: Orte → Knoten, Verbindungen → Kanten.

Behalten: Welche Orte direkt verbunden sind.
Weggelassen: Straßennamen, Gebäude, Maßstab, Kartengrafik.
Warum reicht es? Für Erreichbarkeit, Routenvergleich und Suche sind genau diese Beziehungen entscheidend.

Rückbindung: Der Graph ist kein „Bild der Welt“, sondern ein präzises Modell für algorithmische Fragen.

Grundbegriffe und Eigenschaften
Knoten, Kanten, Nachbarschaft, Gewichtung und Graphentypen

Alle Begriffe werden am selben Beispielgraphen entwickelt:

Ungerichteter Beispielgraph mit Knoten A bis F. — Beispielgraph (ungerichtet): Ausgangspunkt für Knoten, Kanten, Nachbarschaft und Pfade.

Knoten: A, B, C, D, E, F.
Kanten: z. B. A–B, B–D oder D–F sind direkte Verbindungen.
Nachbarn von D: B, C, E, F.
Pfad-Beispiel: A → C → D → F verbindet Start und Ziel über mehrere Kanten.

Derselbe Grundgraph kann nun fachlich variiert werden – erst durch Richtung, dann durch Gewichte:

Gerichtet vs. ungerichtet

Gerichteter Graph mit Pfeilen auf den Kanten zwischen A bis F.

Bei gerichteten Graphen haben Kanten eine Richtung (Einbahnstraßen, gerichtete Beziehungen). Aus A → B folgt dann nicht automatisch B → A.

Gewichtet vs. ungewichtet

Gewichteter Graph mit Kantengewichten zwischen A bis F.

Gewichtete Graphen tragen zusätzliche Kosteninformationen wie Distanz, Zeit oder Preis. Damit wird aus „gibt es einen Weg?“ die Frage „welcher Weg ist optimal?“ – genau die Vorbereitung auf Dijkstra.

Speicherung und Darstellung
Adjazenzmatrix und Adjazenzliste als zentrale Repräsentationen

Derselbe Graph kann in mehreren, gleichwertigen Darstellungen gespeichert werden. Unten siehst du exakt dieselbe Struktur zuerst als Graphbild, dann als Adjazenzliste und schließlich als Adjazenzmatrix.

Beispielgraph mit Knoten A bis F. — 1) Graphdarstellung

Adjazenzliste für die Knoten A bis F. — 2) Adjazenzliste

Adjazenzmatrix

tabellarische Darstellung mit Zeilen und Spalten für alle Knoten
direkter Zugriff auf „Kante vorhanden?“ über festen Index
hoher Speicherbedarf bei großen, dünn besetzten Graphen

Adjazenzliste

zu jedem Knoten eine Liste seiner Nachbarn
speichereffizient bei wenigen Kanten
Zugriff auf konkrete Verbindung meist über Iteration in der Liste

Direkte Zuordnung: Die Knotennamen A–F bleiben in allen drei Darstellungen identisch. Genau deshalb können Algorithmen zwischen Bild, Liste und Matrix wechseln, ohne das Modell zu ändern.

Tiefensuche (DFS, rekursiv)
Tiefenorientierte Graphdurchsuchung mit Backtracking

Gegeben ist ein Startknoten. Die Tiefensuche folgt jeweils einem noch unbesuchten Nachbarn, solange dies möglich ist. Trifft der Algorithmus auf eine Sackgasse, springt er zurück zum letzten Knoten mit offenen Alternativen. Dieses Zurückspringen heißt Backtracking.

In rekursiven Implementierungen entsteht dieses Verhalten durch den Aufrufstapel (Stack-Prinzip). Besuchsmarkierungen verhindern dabei Mehrfachbesuche.

Am Beispielgraphen mit Start A (alphabetische Nachbarreihenfolge) ergibt sich die Besuchsreihenfolge A, B, D, C, E, F. Typischer Tiefenpfad am Anfang: A → B → D → C.

Struktogramm: Tiefensuche (DFS, rekursiv)

Vorlage direkt bearbeiten: DFS im Struktogramm-Tool öffnen.

Breitensuche (BFS)
Ebenenorientierte Suche mit Queue (FIFO-Prinzip)

Die Breitensuche arbeitet schichtweise: Zuerst werden alle direkten Nachbarn des Startknotens betrachtet, danach alle Nachbarn der nächsten Ebene usw. Dafür wird eine Queue (FIFO: first in, first out) verwendet.

Neue, unbesuchte Knoten werden hinten in die Queue eingefügt; verarbeitet wird immer der vorderste Eintrag. So entsteht automatisch die Ebenenstruktur der Suche.

Für denselben Beispielgraphen und Start A ergibt sich bei BFS die Reihenfolge A, B, C, D, E, F. Die Ebenen sind: {A}, dann {B, C}, dann {D, E}, dann {F}.

Struktogramm: Breitensuche (BFS, mit Queue)

Vergleich DFS vs. BFS

Kriterium	DFS	BFS
Suchstruktur	Tiefenorientiert mit Zurückspringen (Backtracking)	Ebenenorientiert (Schicht für Schicht)
Zentrale Datenstruktur	Stack / Rekursion	Queue (FIFO)
Typische Stärke	Strukturerkundung, Pfadsuche mit Tiefe	Kürzeste Wege in ungewichteten Graphen

Beide Verfahren benötigen eine Besuchsmarkierung. Ohne diese Markierung würden Zyklen zu wiederholter Verarbeitung derselben Knoten führen.

Vorlage direkt bearbeiten: BFS im Struktogramm-Tool öffnen.

Ausblick: Kürzeste Wege
Von erreichbaren Wegen zu optimalen Wegen mit Gewichten

Für viele Anwendungen reicht „irgendein erreichbarer Weg“ nicht aus. Gesucht ist der optimale Weg mit minimalen Gesamtkosten.

Sobald Kantengewichte (z. B. Kilometer oder Zeit) entscheidend sind, genügen einfache Suchverfahren allein nicht mehr. Im nächsten Schritt wird deshalb das Prinzip von Dijkstra als Standardverfahren für kürzeste Wege vorbereitet.

Im Struktogramm-Tool steht dafür eine vorbereitete Vorlage bereit: Dijkstra-Grundablauf öffnen.