Bäume, Graphen und Wegsuche

Ein Dateisystem, ein Stammbaum, ein Straßennetz, ein soziales Netzwerk, das Internet: Auf den ersten Blick haben diese fünf nichts gemeinsam.

Auf den zweiten sind sie dasselbe. In allen fünf gibt es Dinge und Verbindungen zwischen ihnen, und alles Weitere folgt daraus.

Genau das leisten Bäume und Graphen: Sie sind keine Datenstrukturen für einen bestimmten Zweck, sondern eine Sprache, in der sich sehr verschiedene Aufgaben formulieren lassen. Wer ein Problem als Graph beschrieben hat, kann fertige Verfahren darauf anwenden, statt jedes Mal neu anzufangen.

Vorausgesetzt werden Feld, verkettete Liste, Stapel und Warteschlange aus Datentypen und Datenstrukturen, Rekursion aus Rekursion und Teile und herrsche sowie die O-Notation.

Ein Baum besteht aus Knoten, die durch Kanten verbunden sind, und hat einen ausgezeichneten Knoten, die Wurzel. Jeder andere Knoten hat genau einen Vorgänger.

                (8)          ← Wurzel, Tiefe 0
               /   \
            (3)     (10)     ← Tiefe 1
           /   \       \
         (1)   (6)     (14)  ← Tiefe 2
              /   \
            (4)   (7)        ← Tiefe 3

Ein Binärbaum ist ein Baum, in dem jeder Knoten höchstens zwei Kinder hat, ein linkes und ein rechtes.

🔴 Beachte, dass ein Baum von Natur aus rekursiv aufgebaut ist: Jedes Kind ist selbst wieder die Wurzel eines Baums. Deshalb sind fast alle Verfahren auf Bäumen rekursiv, und deshalb sind sie kurz.

Ein Binärbaum wird zum binären Suchbaum, wenn für jeden Knoten gilt:

Alle Werte im linken Teilbaum sind kleiner, alle im rechten größer als der Knoten selbst.

Der Baum oben erfüllt das. Prüfe es am Knoten 3: links steht 1 (kleiner), rechts stehen 6, 4, 7 (alle größer). Und am Knoten 8: links 3, 1, 6, 4, 7 (alle kleiner), rechts 10, 14 (größer).

Suchen ist damit dasselbe wie die binäre Suche, nur auf einer Zeigerstruktur:

suche(knoten, x):
    wenn knoten leer:        gib "nicht gefunden"
    wenn knoten.wert = x:    gib gefunden
    wenn x < knoten.wert:    suche(knoten.links, x)
    sonst:                   suche(knoten.rechts, x)

Jeder Vergleich halbiert im günstigen Fall die Möglichkeiten, also $O(\log n)$.

Aber nur im günstigen Fall. Fügt man die Werte $1, 2, 3, 4, 5$ der Reihe nach ein, entsteht kein Baum, sondern eine Kette:

(1)
  \
  (2)
    \
    (3)
      \
      (4)

Die Höhe ist dann $n$ statt $\log n$, und die Suche fällt auf $O(n)$ zurück. Ein binärer Suchbaum ist also nur so gut wie seine Ausgewogenheit. In der Praxis benutzt man deshalb Bauformen, die sich beim Einfügen selbst wieder ausgleichen.

Der Vorteil gegenüber einem sortierten Feld: Einfügen und Löschen kosten $O(\log n)$ statt $O(n)$, weil nichts verschoben werden muss. Genau deshalb benutzen Datenbanken Baumstrukturen für ihre Indizes und keine sortierten Felder.

Um alle Knoten zu besuchen, gibt es drei Reihenfolgen. Sie unterscheiden sich nur darin, wann der Knoten selbst an die Reihe kommt:

Die zweite Zeile ist bemerkenswert: Die symmetrische Reihenfolge liefert die Werte sortiert. Das ist kein Zufall, sondern folgt unmittelbar aus der Suchbaumbedingung. Erst kommt alles Kleinere, dann der Knoten, dann alles Größere, und das gilt auf jeder Ebene.

Ein Graph verallgemeinert den Baum: Knoten und Kanten, aber ohne Wurzel, ohne Richtungsvorgabe und mit erlaubten Kreisen.

      A ───── B
      │  \    │
      │   \   │
      C ─── D─┘
       \   /
         E

Ein Baum ist ein Sonderfall: ein zusammenhängender Graph ohne Kreise.

Adjazenzmatrix: eine Tabelle mit einer Zeile und einer Spalte je Knoten; 1 bedeutet „Kante vorhanden".

      A  B  C  D  E
   A  0  1  1  1  0
   B  1  0  0  1  0
   C  1  0  0  1  1
   D  1  1  1  0  1
   E  0  0  1  1  0

Adjazenzliste: für jeden Knoten eine Liste seiner Nachbarn.

A: B, C, D
B: A, D
C: A, D, E
D: A, B, C, E
E: C, D

Dabei ist $m$ die Zahl der Kanten. Für ein Straßennetz mit einer Million Kreuzungen wäre die Matrix mit $10^{12}$ Einträgen unbrauchbar, während die Liste nur die wenigen tatsächlich vorhandenen Straßen speichert. Deshalb ist die Liste in der Praxis der Normalfall.

Um alle erreichbaren Knoten zu besuchen, gibt es zwei Grundverfahren. Sie unterscheiden sich in einem einzigen Punkt, nämlich der verwendeten Datenstruktur:

Tiefensuche benutzt einen Stapel: Man geht so weit wie möglich in eine Richtung und kehrt erst um, wenn es nicht weitergeht. Rekursion erledigt das von selbst, denn der Aufrufstapel ist der Stapel.

Breitensuche benutzt eine Warteschlange: Man besucht erst alle direkten Nachbarn, dann deren Nachbarn, also Ebene für Ebene.

besuche(start):
    lege start in die Struktur
    solange Struktur nicht leer:
        knoten = entnehmen
        wenn knoten schon markiert: weiter
        markiere knoten
        lege alle Nachbarn hinein

Derselbe Ablauf mit einem Stapel ergibt die Tiefensuche, mit einer Warteschlange die Breitensuche. Das ist ein bemerkenswerter Befund: Die Wahl der Datenstruktur bestimmt das Verhalten des Verfahrens.

🔴 Der wichtige Unterschied in der Anwendung: Die Breitensuche findet in einem ungewichteten Graphen den Weg mit den wenigsten Kanten. Sie erreicht jeden Knoten zuerst über den kürzesten Kantenweg, weil sie Ebene für Ebene vorgeht. Die Tiefensuche findet irgendeinen Weg, meist nicht den kürzesten; sie eignet sich dafür gut zum Erkennen von Kreisen und zum vollständigen Durchsuchen.

Die Markierung besuchter Knoten ist nicht optional. Ohne sie läuft das Verfahren in einem Graphen mit Kreisen endlos, denn anders als beim Baum kann man zu einem bereits besuchten Knoten zurückkehren.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Sobald Kanten Gewichte tragen, genügt die Breitensuche nicht mehr. Der Weg mit den wenigsten Kanten ist nicht der kürzeste, wenn eine einzelne Kante sehr lang ist.

Das Verfahren von Dijkstra löst das:

1. Alle Knoten bekommen die vorläufige Entfernung $\infty$, der Startknoten die 0. 2. Wähle unter den noch nicht abgeschlossenen Knoten den mit der kleinsten vorläufigen Entfernung. 3. Prüfe für jeden seiner Nachbarn, ob der Weg über den gewählten Knoten kürzer ist als die bisher bekannte Entfernung. Wenn ja, trage die neue Entfernung ein. 4. Markiere den Knoten als abgeschlossen und wiederhole ab 2.

Der entscheidende Gedanke steckt in Schritt 2. Warum darf man den Knoten mit der kleinsten vorläufigen Entfernung als endgültig ansehen? Weil jeder andere Weg dorthin über einen Knoten führen müsste, der bereits weiter entfernt ist, und da alle Gewichte nicht negativ sind, kann ein solcher Weg nur länger werden.

An dieser Begründung hängt auch die Voraussetzung: Das Verfahren setzt nichtnegative Gewichte voraus. Gäbe es negative Kanten, könnte ein Umweg die Gesamtstrecke verkürzen, und die Annahme fiele in sich zusammen.

Jedes Navigationsgerät arbeitet im Kern so, mit Fahrzeit oder Entfernung als Gewicht.