Q1.5 – Graphen als Netzmodelle

Q1.5 gehört zum Leistungskurs. Im Kern steht nicht nur, Graphbegriffe zu benennen, sondern ein Netzproblem so zu modellieren, dass es mit bekannten Datenstrukturen und Graphalgorithmen bearbeitbar wird.

Ein Baum aus Q1.4 ist bereits eine Struktur aus Knoten und Kanten. Er besitzt aber eine besondere Ordnung: Es gibt eine Wurzel, eine Hierarchie aus Eltern- und Kindknoten und in einem Baum meist genau einen Pfad von der Wurzel zu einem Knoten.

Ein Graph verallgemeinert diese Idee. Er braucht keine feste Wurzel, Knoten können beliebig viele Nachbarn besitzen, Zyklen sind möglich, und zwischen zwei Knoten können mehrere verschiedene Wege liegen. Zusätzlich können Kanten gerichtet sein oder Gewichte wie Entfernung, Dauer oder Kosten tragen.

Damit bleiben Q1.3 und Q1.4 fachlich wirksam: DFS nutzt Rekursion, Stack-Prinzip und Backtracking; BFS nutzt die Queue; die Adjazenzliste nutzt eine Liste von Objekten und Referenzen.

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 Kontextinformationen. Für die Routenplanung reichen zunächst Orte, Verbindungen und gegebenenfalls Entfernungen oder Fahrzeiten.

Dasselbe Modellierungsprinzip trägt auch andere Anwendungen:

Ein Graph entsteht also durch Abstraktion: Objekte oder Situationen werden zu Knoten, Beziehungen zu Kanten, Richtung zu gerichteten Kanten und Kosten zu Gewichten. Die Fragestellung entscheidet, welche Details weggelassen werden dürfen.

Die Begriffe werden nicht isoliert auswendig gelernt. Sie entstehen aus Fragen an denselben Beispielgraphen:

Bei gerichteten Graphen wird zusätzlich zwischen Eingangsgrad und Ausgangsgrad unterschieden: Eingehende Kanten zeigen auf einen Knoten, ausgehende Kanten starten an diesem Knoten. Bei gewichteten Graphen zählt für Kostenfragen nicht nur die Anzahl der Kanten, sondern die Summe ihrer Gewichte.

Gerichtet vs. ungerichtet

Bei gerichteten Graphen haben Kanten eine Richtung. Aus A → B folgt dann nicht automatisch, dass auch B → A erlaubt ist.

Gewichtet vs. ungewichtet

Gewichte beschreiben Kosten wie Entfernung, Zeit oder Preis. Sie verändern die Frage nach dem kürzesten Weg, weil wenige Kanten nicht automatisch geringe Kosten bedeuten.

Ein Graphbild ist für Menschen gut lesbar: Es zeigt Knoten, Kanten und Muster auf einen Blick. Ein Computer braucht dagegen eine Datenstruktur. Diese Datenstruktur muss festlegen, wie Nachbarn, Kanten und Gewichte gespeichert und von Algorithmen abgefragt werden.

Für Q1.5 steht die Adjazenzliste im Mittelpunkt. Die Matrix bleibt wichtig als Vergleichsdarstellung: Sie macht Kantenabfragen direkt sichtbar, ist aber nicht die curriculare Hauptmodellierung.

Q1.5 ist keine neue Welt neben Q1.1 und Q1.4. Ein Knoten kann als Objekt modelliert werden, ein Graph verwaltet eine Liste von Knoten, und jeder Knoten besitzt wiederum eine Liste seiner Nachbarn. Genau dadurch entsteht eine objektorientierte Adjazenzliste.

class Knoten {
  String name;
  List<Knoten> nachbarn;
}

class Graph {
  List<Knoten> knoten;
}

class Kante {
  Knoten ziel;
  int gewicht;
}

class Knoten {
  String name;
  List<Kante> kanten;
}

Die bekannte Bibliotheksklasse List aus Q1.1/Q1.4 wird hier wiederverwendet. Die Queue aus Q1.4 wird später bei BFS gebraucht. Graphmodellierung kombiniert also bekannte Ideen: Objekte, Referenzen, Listen und eine passende Zugriffsdatenstruktur.

Die Tiefensuche verfolgt ein einfaches Ziel: Alle von einem Startknoten erreichbaren Knoten besuchen oder einen Pfad zu einem Ziel finden. Ihre Grundidee lautet: Gehe so weit wie möglich in die Tiefe. Wenn es nicht weitergeht, springe zurück zum letzten Knoten mit einer offenen Alternative.

In Graphen ist eine Besuchsmarkierung unverzichtbar. Ohne visited könnte ein Zyklus dazu führen, dass der Algorithmus immer wieder dieselben Knoten besucht. Rekursive DFS nutzt dafür den Aufrufstapel aus Q1.3; eine iterative Variante könnte einen expliziten Stack aus Q1.4 verwenden.

Trace ab A bei alphabetischer Nachbarreihenfolge

Daraus entsteht die Besuchsreihenfolge A, B, D, C, E, F. Wichtiger als die fertige Reihenfolge ist der Mechanismus: Ein Pfad wird vertieft, Sackgassen erzeugen Rücksprünge, und visited schützt vor Endlosschleifen.

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

Die Breitensuche verfolgt denselben Startpunkt wie DFS, arbeitet aber anders: Sie besucht Knoten schichtweise. Zuerst kommt der Startknoten, dann alle Knoten mit Entfernung 1, danach alle Knoten mit Entfernung 2 und so weiter.

Die zentrale Datenstruktur ist die Queue aus Q1.4. Der Startknoten wird eingefügt, vorne wird immer der nächste Knoten entnommen, und unbesuchte Nachbarn werden hinten angefügt. visited verhindert, dass ein Knoten mehrfach in die Queue gelangt.

Queue-Trace ab A

Die Ebenen sind {A}, dann {B, C}, dann {D, E}, dann {F}. Genau diese Ebenenstruktur erklärt, warum BFS in ungewichteten Graphen kürzeste Wege nach Kantenzahl findet.

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

In ungewichteten Graphen oder Graphen mit gleichen Kantengewichten bedeutet "kürzester Weg": möglichst wenige Kanten. BFS passt genau dazu, weil der Algorithmus zuerst Entfernung 0, dann Entfernung 1, dann Entfernung 2 usw. betrachtet. Der erste Fund eines Knotens liefert daher einen kürzesten Weg in Kantenzahl.

Für die Wegrekonstruktion reicht es nicht, nur visited zu speichern. Zusätzlich wird für jeden neu entdeckten Knoten ein Vorgänger notiert: Von welchem Knoten aus wurde er zuerst erreicht?

vorgaenger[B] = A;
vorgaenger[C] = A;
vorgaenger[D] = B;
vorgaenger[E] = C;
vorgaenger[F] = D;

Pfad von A nach F rekonstruieren

Ergebnis: A → B → D → F ist ein kürzester Weg mit drei Kanten. Je nach Reihenfolge kann BFS einen anderen, aber gleich kurzen Pfad liefern.

BFS findet kürzeste Wege, wenn jede Kante gleich viel zählt. Sobald Kanten unterschiedliche Gewichte tragen, reicht diese Logik nicht mehr: Ein Weg mit wenigen Kanten kann teurer sein als ein Weg mit mehreren günstigen Kanten.

Für solche Fälle braucht man Verfahren wie Dijkstra. Auf dieser Seite bleibt Dijkstra bewusst Ausblick: Der Pflichtkern von Q1.5 ist die Modellierung mit Adjazenzlisten sowie DFS, BFS und kürzeste Wege mit BFS in ungewichteten Graphen.

Ausblick im Struktogramm-Tool: Dijkstra-Grundablauf öffnen.

Am Ende von Q1.5 steht keine einzelne "beste" Darstellung. Fachlich stark ist die begründete Entscheidung: Welches Netz wird modelliert, welche Informationen müssen gespeichert werden und welches Verfahren passt zur Frage?