Ein Graph $G = (V, E)$ besteht aus einer endlichen Menge $V$ von Knoten und einer Menge $E$ von Kanten. In einem ungerichteten Graphen ist eine Kante $\{u, v\}$ eine Verbindung zwischen zwei Knoten ohne Richtung. In einem gerichteten Graphen hat jede Kante $(u, v)$ eine Richtung von $u$ nach $v$.

Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart. Ein Weg ist eine Folge von Knoten, in der aufeinanderfolgende Knoten benachbart sind. Seine Länge ist die Zahl der Kanten. Ein Graph heißt zusammenhängend, wenn es von jedem Knoten einen Weg zu jedem anderen gibt.

Zur Darstellung im Computer speichert man für jeden Knoten die Liste seiner Nachbarn (Adjazenzliste) oder eine $|V| \times |V|$-Tabelle mit Einträgen $1$ für vorhandene Kanten (Adjazenzmatrix). Die Liste braucht Platz $O(|V| + |E|)$, die Matrix $O(|V|^2)$. Für Graphen mit wenigen Kanten ist die Liste besser.

Bei der Breitensuche startest du an einem Knoten $s$ und besuchst zuerst alle seine Nachbarn, dann deren Nachbarn und so weiter. Du erkundest den Graphen also Schicht für Schicht, wie Wellen um einen ins Wasser geworfenen Stein.

Technisch benutzt man eine Warteschlange (Queue: wer zuerst kommt, wird zuerst bearbeitet). Du legst $s$ hinein und markierst ihn. Solange die Schlange nicht leer ist, nimmst du den vordersten Knoten heraus, und jeden unmarkierten Nachbarn markierst du und stellst ihn hinten an.

Wichtige Eigenschaft: Die Breitensuche findet in einem Graphen ohne Gewichte zu jedem erreichbaren Knoten einen kürzesten Weg (gemessen in Kanten), denn Knoten mit kleinerem Abstand werden vor Knoten mit größerem Abstand bearbeitet. Die Laufzeit ist $O(|V| + |E|)$.

Bei der Tiefensuche folgst du von $s$ aus einem Nachbarn, von dort einem weiteren Nachbarn und so weiter, so tief wie möglich. Erst wenn es nicht weitergeht (alle Nachbarn sind besucht), gehst du einen Schritt zurück und probierst die nächste Möglichkeit. Das ist wie das Erkunden eines Labyrinths mit einem Faden.

Technisch benutzt man einen Stapel (Stack: zuletzt hinein, zuerst heraus) oder die Rekursion, die einen Stapel implizit mitbringt. Die Laufzeit ist ebenfalls $O(|V| + |E|)$. Die Tiefensuche findet nicht unbedingt kürzeste Wege, ist aber die Grundlage für Zykluserkennung, die Zerlegung in Zusammenhangskomponenten und die topologische Sortierung.