Ein Binärbaum besteht aus Knoten. Der oberste ist die Wurzel. Jeder Knoten hat höchstens zwei Kinder, ein linkes und ein rechtes. Knoten ohne Kinder sind Blätter. Jeder Knoten ist die Wurzel eines Teilbaums. Die Höhe ist die Zahl der Kanten auf dem längsten Weg von der Wurzel zu einem Blatt.

Ein geordneter Binärbaum (binärer Suchbaum) hat in jedem Knoten nur kleinere Werte im linken und nur größere im rechten Teilbaum. Suchen und Einfügen gehen links oder rechts weiter, höchstens so oft, wie die Höhe angibt: $O(\log n)$ Schritte bei einem ausgeglichenen Baum mit $n$ Knoten, $O(n)$ bei einem entarteten, der zur Liste wird (etwa nach dem Einfügen einer sortierten Folge).

Der Baum, der beim Einfügen von 8, 3, 10, 1, 6, 14, 4 entsteht:

Die Traversierung besucht jeden Knoten genau einmal. Die drei Tiefenreihenfolgen unterscheiden sich darin, wann die Wurzel eines Teilbaums an der Reihe ist. Die Teilbäume durchläuft man nach derselben Regel, also rekursiv.

• Preorder: Wurzel, linker Teilbaum, rechter Teilbaum.
• Inorder: linker Teilbaum, Wurzel, rechter Teilbaum.
• Postorder: linker Teilbaum, rechter Teilbaum, Wurzel.

Als Funktion: $\texttt{inorder(k)}$ tut nichts, wenn k gleich $\texttt{None}$ ist. Sonst ruft es $\texttt{inorder(k.links)}$ auf, gibt $\texttt{k.wert}$ aus und ruft $\texttt{inorder(k.rechts)}$ auf.

Ein Graph besteht aus Knoten und Kanten, die je zwei Knoten verbinden. Kanten eines gerichteten Graphen haben eine Richtung (Einbahnstraßen), die eines ungerichteten nicht. Bei einem gewichteten Graphen trägt jede Kante eine Zahl, etwa die Fahrzeit. Ein Weg ist eine Folge von Knoten, bei der aufeinanderfolgende durch Kanten verbunden sind, seine Länge ist die Summe der Gewichte. Ein Zyklus ist ein Weg, der am Startknoten endet und keine Kante zweimal benutzt. Ein Baum ist ein zusammenhängender ungerichteter Graph ohne Zyklus, mit $n$ Knoten und $n - 1$ Kanten.

Die Adjazenzmatrix hat je eine Zeile und Spalte pro Knoten. In Zeile A und Spalte B steht das Gewicht der Kante von A nach B oder ein Zeichen für „keine Kante“. Sie braucht $n^2$ Zellen, und ob eine Kante existiert, sieht man in $O(1)$. Die Adjazenzliste speichert für jeden Knoten seine Nachbarn mit den Gewichten. Mit $m$ Kanten braucht sie $O(n + m)$ Platz und lohnt sich bei wenigen Kanten.

Im Stadtplan sind die Knoten Kreuzungen, die Gewichte Fahrzeiten in Minuten. Kanten: A-B 4, A-C 2, B-D 5, B-E 10, C-D 8, C-F 9, D-E 3, D-F 6, E-G 4, F-G 2, F-H 3, G-H 7.

Beide Verfahren besuchen alle Knoten, die vom Startknoten aus erreichbar sind, und markieren besuchte Knoten, damit ein Zyklus keine Endlosschleife erzeugt. Die Breitensuche besucht erst alle Nachbarn des Startknotens, dann deren Nachbarn und so weiter. Sie merkt sich offene Knoten in einer Warteschlange und findet Wege mit den wenigsten Kanten. Die Tiefensuche geht immer zu einem unbesuchten Nachbarn, so weit es geht, und kehrt dann zurück (Backtracking). Sie nutzt einen Stapel oder Rekursion. Beide brauchen mit einer Adjazenzliste $O(n + m)$ Schritte.

Im Stadtplan ab A, Nachbarn alphabetisch, besucht die Breitensuche A, B, C, D, E, F, G, H und die Tiefensuche A, B, D, C, F, G, E, H.

Gesucht ist der kürzeste Weg von einem Startknoten zu den anderen Knoten. Dijkstra setzt Gewichte von mindestens 0 voraus. Jeder Knoten hat eine vorläufige Entfernung $d$ (am Start 0, sonst unendlich). Dijkstra schließt wiederholt den offenen Knoten $u$ mit kleinstem $d$ ab: Seine Entfernung ist nun endgültig. Dann prüft er jede Kante von $u$ zu einem Nachbarn $v$ mit Gewicht $w$ und setzt $d(v)$ auf $d(u) + w$, wenn das kleiner ist, und merkt sich $u$ als Vorgänger. Die Wahl des kleinsten $d$ ist richtig, weil bei Gewichten von mindestens 0 kein späterer Umweg einen abgeschlossenen Knoten verbessert. Mit einer Datenstruktur, die den kleinsten Wert schnell findet, braucht Dijkstra $O((n + m) \log n)$ Schritte.

Bellman-Ford prüft in $n - 1$ Runden jede Kante auf dieselbe Weise. Es erlaubt negative Gewichte und erkennt einen negativen Zyklus: Verbessert sich in Runde $n$ noch ein Wert, gibt es einen. Es braucht $O(n \cdot m)$ Schritte.

Ein Spannbaum eines zusammenhängenden ungerichteten Graphen ist ein Baum, der alle Knoten verbindet, er hat $n - 1$ Kanten. Ein minimaler Spannbaum hat die kleinste Summe der Gewichte, wie das billigste Leitungsnetz, das alle Orte verbindet. Prim beginnt an einem Knoten und fügt immer die billigste Kante hinzu, die einen neuen Knoten an den Baum anschließt. Kruskal geht alle Kanten nach aufsteigendem Gewicht durch und nimmt jede, die keinen Zyklus schließt. Beide wählen in jedem Schritt lokal das Billigste (Greedy, siehe unten).

Im Stadtplan wählen beide A-C (2), F-G (2), D-E (3), F-H (3), A-B (4), E-G (4) und B-D (5). Das Gesamtgewicht ist 2 + 2 + 3 + 3 + 4 + 4 + 5 = 23.

Ein Greedy-Verfahren trifft in jedem Schritt die lokal beste Wahl und nimmt sie nie zurück. Das führt nicht immer zum Optimum. Wechselgeld für 6 mit Münzen 1, 3 und 4: Greedy nimmt 4, 1, 1 (drei Münzen), optimal sind 3 und 3. Bei Dijkstra, Prim und Kruskal führt die lokale Wahl nachweislich zum Optimum.

Viele Aufgaben sind eine Suche in einem Suchraum, der selbst ein Graph ist: Knoten sind Zustände (eine Stellung beim Schiebepuzzle, ein Ort auf der Karte), Kanten sind erlaubte Züge. Gesucht ist ein Weg vom Start- zu einem Zielzustand. Breiten- und Tiefensuche wissen nichts über das Ziel, und der Raum wächst oft sehr schnell.

Der A*-Algorithmus ist eine informierte Suche. Er nutzt eine Heuristik $h(v)$, eine Schätzung der Restkosten von $v$ zum Ziel, etwa die Luftlinie. Wie Dijkstra wählt er den Knoten mit kleinstem $f(v) = g(v) + h(v)$, wobei $g(v)$ die bisherigen Kosten vom Start sind. Ist $h$ nie größer als die wahren Restkosten, findet A* einen kürzesten Weg.