Tiefen- und Breitensuche – die Standardverfahren zum Durchlaufen von Graphen – sind Grundlage für viele Graphenalgorithmen wie z. B. die Konstruktion von Spannbäumen und Ringen (Kreisen) und die Suche nach kürzesten Wegen. Wegen ihrer Bedeutung werden in diesem Kapitel Techniken zur Konstruktion von Algorithmen zur Tiefen- und zur Breitensuche in verteilten Graphen entwickelt. Sie liefern die entsprechenden Spannbäume und Tiefensuche ermöglicht es auch, Kreise zu finden. In vielen Lehrbüchern über Verteilte Programmierung werden nur die Prinzipien der Algorithmen dargestellt, ohne auf konkrete Realisierungen einzugehen. Der nennenswerte Aufwand dafür in diesem Kapitel zeigt, dass das keineswegs vernachlässigbar ist.